Hierarchical planarity testing algorithms

DOI10.1145/65950.65952MaRDI QIDQ4710683zbMATH OpenOpenAlexFDO

Authors Thomas Lengauer

Publication date 25 June 1992

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 3960992
• scientific article; zbMATH DE number 4049078
• Hierarchies and planarity theory
• The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
• Efficient algorithms for finding minimum spanning forests of hierarchically defined graphs

Cited in

(29)

• scientific article; zbMATH DE number 1796981 (Why is no real title available?)
• Using the metro-map metaphor for drawing hypergraphs
• scientific article; zbMATH DE number 4049078 (Why is no real title available?)
• On embedding a cycle in a plane graph
• Structure-preserving hierarchical decompositions
• Fast incremental planarity testing
• Model-checking hierarchical structures
• scientific article; zbMATH DE number 6863594 (Why is no real title available?)
• scientific article; zbMATH DE number 6863595 (Why is no real title available?)
• Bounded Embeddings of Graphs in the Plane
• Hierarchically specified unit disk graphs
• Beyond Clustered Planar Graphs
• scientific article; zbMATH DE number 1500509 (Why is no real title available?)
• The complexity of combinatorial problems with succinct input representation
• The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
• Constrained planarity in practice -- engineering the synchronized planarity algorithm
• Hierarchically specified unit disk graphs
• scientific article; zbMATH DE number 3960992 (Why is no real title available?)
• Synchronized Planarity with Applications to Constrained Planarity Problems
• Clustered planarity testing revisited
• Atomic Embeddability, Clustered Planarity, and Thickenability
• The complexity of approximating \(\mathrm{PSPACE}\)-complete problems for hierarchical specifications
• A new perspective on clustered planarity as a combinatorial embedding problem
• Hierarchies and planarity theory
• On Radiocoloring Hierarchically Specified Planar Graphs: $$\mathcal{PSPACE}$$ -completeness and Approximations
• Exact algorithms for clustered planarity with linear saturators
• Simultaneous Embedding
• Orthogonal drawings of graphs for the automation of VLSI circuit design
• Fixpoint logics over hierarchical structures

This page was built for publication: Hierarchical planarity testing algorithms

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