Fully dynamic planarity testing with applications

DOI10.1145/300515.300517MaRDI QIDQ3158532zbMATH OpenOpenAlexFDO

Authors Giuseppe F. Italiano, Neil Sarnak, Zvi Galil

Publication date 25 January 2005

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/300515.300517

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 176746
• On-Line Planarity Testing
• scientific article; zbMATH DE number 1256640
• Separator based sparsification. I: Planarity testing and minimum spanning trees
• Improved data structures for fully dynamic biconnectivity

Cited in

(19)

• Dynamic planar embeddings of dynamic graphs
• Separator based sparsification. I: Planarity testing and minimum spanning trees
• Heuristics for the maximum outerplanar subgraph problem
• Alpha-algorithms for incremental planarity testing (extended abstract)
• Dynamic planar embeddings of dynamic graphs
• scientific article; zbMATH DE number 176746 (Why is no real title available?)
• Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time
• On-Line Planarity Testing
• A simulated annealing algorithm for the maximum planar subgraph problem
• The power of vertex sparsifiers in dynamic graph algorithms
• Fully-dynamic planarity testing in polylogarithmic time
• Fast incremental planarity testing
• A fully dynamic algorithm for planar
• Faster shortest-path algorithms for planar graphs
• Certificates and fast algorithms for biconnectivity in fully-dynamic graphs
• Fully dynamic maintenance of vertex cover
• Good \(r\)-divisions imply optimal amortized decremental biconnectivity
• Dynamic and static algorithms for optimal placement of resources in a tree
• Good r-divisions imply optimal amortized decremental biconnectivity

This page was built for publication: Fully dynamic planarity testing with applications

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