Streamed Graph Drawing and the File Maintenance Problem

DOI10.1007/978-3-319-03841-4_23MaRDI QIDQ2867663zbMATH OpenOpenAlexFDO

Authors Paweł Pszona, Michael T. Goodrich

Publication date 20 December 2013

Published in Graph Drawing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.6711

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Abstract: In streamed graph drawing, a planar graph, G, is given incrementally as a data stream and a straight-line drawing of G must be updated after each new edge is released. To preserve the mental map, changes to the drawing should be minimized after each update, and Binucci et al.show that exponential area is necessary and sufficient for a number of streamed graph drawings for trees if edges are not allowed to move at all. We show that a number of streamed graph drawings can, in fact, be done with polynomial area, including planar streamed graph drawings of trees, tree-maps, and outerplanar graphs, if we allow for a small number of coordinate movements after each update. Our algorithms involve an interesting connection to a classic algorithmic problem - the file maintenance problem - and we also give new algorithms for this problem in a framework where bulk memory moves are allowed.

Recommendations

• On graph problems in a semi-streaming model
• Automata, Languages and Programming
• Dynamic graph stream algorithms in \(o(n)\) space
• Dynamic graph stream algorithms in \(o(n)\) space
• A Survey of Graph Algorithms Under Extended Streaming Models of Computation
• Trading off space for passes in graph streaming problems
• Graph spanners in the streaming model: An experimental study
• Labeled graph sketches: keeping up with real-time graph streams
• Graph sketching and streaming: new approaches for analyzing massive graphs
• Area-efficient static and incremental graph drawings

Cited in

(9)

• Graph stories in small area
• Labeled graph sketches: keeping up with real-time graph streams
• Drawing trees in a streaming model
• Drawing trees in a streaming model
• Graph Stories in Small Area
• Small Point-Sets Supporting Graph Stories
• Small point-sets supporting graph stories
• The variable-processor cup game
• Geometry matters in planar storyplans

This page was built for publication: Streamed Graph Drawing and the File Maintenance Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2867663)