Dynamic planar embeddings of dynamic graphs

DOI10.1007/S00224-017-9768-7MaRDI QIDQ1693993zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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 theorydata structuresgraph algorithmsplanar graphsgraph embeddingsdynamic data structures

Mathematics Subject Classification ID

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

Recommendations

• Dynamic planar embeddings of dynamic graphs
• On-line Planar Graph Embedding
• scientific article; zbMATH DE number 4060744
• Fully dynamic planarity testing with applications
• scientific article; zbMATH DE number 176746

Cites work

• scientific article; zbMATH DE number 3882430 (Why is no real title available?)
• scientific article; zbMATH DE number 2079390 (Why is no real title available?)
• A data structure for dynamic trees
• Alpha-algorithms for incremental planarity testing (extended abstract)
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Efficient Planarity Testing
• Fast incremental planarity testing
• Fully dynamic planarity testing with applications
• How to Draw a Graph
• Incremental convex planarity testing
• Logarithmic Lower Bounds in the Cell-Probe Model
• Maintaining information in fully dynamic trees with top trees
• Maintenance of a minimum spanning forest in a dynamic plane graph
• Multiple-source shortest paths in planar graphs
• On-Line Planarity Testing
• Random sampling in cut, flow, and network design problems
• Separator based sparsification. I: Planarity testing and minimum spanning trees

Cited in

(6)

• Worst-case deterministic fully-dynamic biconnectivity in changeable planar embeddings
• Decremental SPQR-trees for Planar Graphs
• Dynamic planar embeddings of dynamic graphs
• Dynamic compact planar embeddings
• Dynamic maintenance of planar digraphs, with applications
• scientific article; zbMATH DE number 4060744 (Why is no real title available?)

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

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