Alpha-algorithms for incremental planarity testing (extended abstract)

DOI10.1145/195058.195439MaRDI QIDQ2817665zbMATH OpenOpenAlexFDO

Authors Johannes A. La Poutré

Publication date 1 September 2016

Published in Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Fast incremental planarity testing
• On-Line Planarity Testing
• On-line Planar Graph Embedding
• A Linear-Time Algorithm for Finding a Maximal Planar Subgraph
• Fully dynamic planarity testing with applications

Cited in

(17)

• Dynamic planar embeddings of dynamic graphs
• Incremental convex planarity testing
• Graph stories in small area
• An analysis of heuristics for graph planarization
• On-Line Planarity Testing
• A linear algorithm for the maximal planar subgraph problem
• Maintenance of triconnected components of graphs
• Certificates and fast algorithms for biconnectivity in fully-dynamic graphs
• Planarization of graphs embedded on surfaces
• Small Point-Sets Supporting Graph Stories
• Small point-sets supporting graph stories
• On-line convex planarity testing
• A linear time algorithm for finding maximal planar subgraphs
• Improved dynamic colouring of sparse graphs
• Dynamic embeddings of dynamic single-source upward planar graphs
• Exact algorithms for clustered planarity with linear saturators
• A branch-and-cut approach to the crossing number problem

This page was built for publication: Alpha-algorithms for incremental planarity testing (extended abstract)

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