Back to Search
Start Over
Drawing trees in a streaming model
- Source :
- Graph Drawing ISBN: 9783642118043, Graph Drawing
- Publication Year :
- 2010
-
Abstract
- We pose a new visualization challenge, asking Graph Drawing algorithms to cope with the requirements of Streaming applications. In this model a source produces a graph one edge at a time. When an edge is produced, it is immediately drawn and its placement cannot be altered. The drawing has an image persistence, that controls the lifetime of edges. If the persistence is k, an edge remains in the drawing for the time spent by the source to generate k edges, and then it fades away. In this model we study the area requirement of planar straight-line grid drawings of trees and we assess the output quality of the presented algorithms by computing the competitive ratio with respect to the best known offline algorithms.
- Subjects :
- Data stream
Design of algorithms
Graph algorithms
Online algorithms
Graph drawing
Streaming
Large graphs
SPQR tree
Theoretical computer science
Computer science
Graph Drawing
Strength of a graph
Theoretical Computer Science
ComputingMilieux_COMPUTERSANDEDUCATION
Large Graphs
Competitive analysis
Model of computation
Grid
Feedback arc set
Computer Science Applications
Graph bandwidth
Signal Processing
Graph (abstract data type)
Image persistence
Force-directed graph drawing
ddc:004
MathematicsofComputing_DISCRETEMATHEMATICS
Information Systems
Subjects
Details
- Language :
- English
- ISBN :
- 978-3-642-11804-3
- ISBNs :
- 9783642118043
- Database :
- OpenAIRE
- Journal :
- Graph Drawing ISBN: 9783642118043, Graph Drawing
- Accession number :
- edsair.doi.dedup.....fe0bbc13f6fd43dc383f093d735f5242