Dynamic planar embeddings of dynamic graphs

DOI10.1007/s00224-017-9768-7zbMath1387.68182OpenAlexW2275934214WikidataQ61414891 ScholiaQ61414891MaRDI QIDQ1693993

Jacob Holm, Eva Rotenberg

Publication date: 1 February 2018

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/4931/

zbMATH Keywords

graph theoryplanar graphsdata structuresgraph algorithmsgraph embeddingsdynamic data structures

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items (1)

Decremental SPQR-trees for Planar Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A data structure for dynamic trees
• Incremental convex planarity testing
• Separator based sparsification. I: Planarity testing and minimum spanning trees
• Random sampling in cut, flow, and network design problems
• Alpha-algorithms for incremental planarity testing (preliminary version)
• Maintaining information in fully dynamic trees with top trees
• Fully dynamic planarity testing with applications
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Maintenance of a minimum spanning forest in a dynamic plane graph
• Efficient Planarity Testing
• On-Line Planarity Testing
• Fast incremental planarity testing
• Logarithmic Lower Bounds in the Cell-Probe Model
• How to Draw a Graph

This page was built for publication: Dynamic planar embeddings of dynamic graphs