Planarity for clustered graphs

DOI10.1007/3-540-60313-1_145zbMath1512.68214OpenAlexW1487870695MaRDI QIDQ6102302

Qingwen Feng, Peter Eades, R. F. Cohen

Publication date: 8 May 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-60313-1_145

Mathematics Subject Classification ID

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

Related Items

How to draw the minimum cuts of a planar graph ⋮ Using the metro-map metaphor for drawing hypergraphs ⋮ Advances on Testing C-Planarity of Embedded Flat Clustered Graphs ⋮ Atomic Embeddability, Clustered Planarity, and Thickenability ⋮ Towards the Hanani-Tutte Theorem for Clustered Graphs ⋮ Drawing \(c\)-planar biconnected clustered graphs ⋮ Clustered planarity with pipes ⋮ How to draw a planar clustered graph ⋮ Synchronized Planarity with Applications to Constrained Planarity Problems ⋮ Clustered planarity testing revisited ⋮ A new perspective on clustered planarity as a combinatorial embedding problem ⋮ \(c\)-planarity of embedded cyclic \(c\)-graphs ⋮ Treetopes and their graphs ⋮ Straight-line rectangular drawings of clustered graphs ⋮ Embedding graphs into embedded graphs ⋮ An SPQR-tree-like embedding representation for upward planarity ⋮ Parameterized complexity of graph planarity with restricted cyclic orders ⋮ Non-crossing Paths with Geographic Constraints ⋮ Clustered planarity = flat clustered planarity ⋮ Completely connected clustered graphs ⋮ Crossing minimization in perturbed drawings ⋮ Simpler algorithms for testing two-page book embedding of partitioned graphs ⋮ Strip planarity testing for embedded planar graphs ⋮ Crossing minimization in perturbed drawings ⋮ Relaxing the constraints of clustered planarity ⋮ Hanani-Tutte for approximating maps of graphs ⋮ Parameterized complexity of graph planarity with restricted cyclic orders ⋮ Clustered Planarity: Clusters with Few Outgoing Edges ⋮ Computing Maximum C-Planar Subgraphs ⋮ Clustered Planarity: Embedded Clustered Graphs with Two-Component Clusters ⋮ C-planarity testing of embedded clustered graphs with bounded dual carving-width ⋮ On embedding a cycle in a plane graph ⋮ Drawing Clustered Planar Graphs on Disk Arrangements ⋮ How to draw a clustered tree ⋮ Beyond Clustered Planar Graphs ⋮ Simultaneous Embedding ⋮ Advancements on SEFE and partitioned book embedding problems ⋮ Embedding Graphs into Embedded Graphs ⋮ Planarity-preserving clustering and embedding for large planar graphs

Cites Work

• A linear algorithm for embedding planar graphs using PQ-trees
• Planar graphs: Theory and algorithms
• Computing an st-numbering
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Crossing Number is NP-Complete
• A Depth-First-Search Characterization of Planarity
• Efficient Planarity Testing
• Unnamed Item
• Unnamed Item
• Unnamed Item