Advances on testing C-planarity of embedded flat clustered graphs

DOI10.1142/S0129054119500011MaRDI QIDQ5384459zbMATH OpenOpenAlexWikidataFDO

Authors Markus Chimani, Giuseppe Di Battista, Fabrizio Frati, Karsten Klein

Publication date 24 June 2019

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.2595

zbMATH Keywords

graph drawingclustered planarityplanar embedding

Mathematics Subject Classification ID

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

Abstract: We show a polynomial-time algorithm for testing c-planarity of embedded flat clustered graphs with at most two vertices per cluster on each face.

Recommendations

• Efficient \(C\)-planarity testing for embedded flat clustered graphs with small faces
• Efficient C-Planarity Testing for Embedded Flat Clustered Graphs with Small Faces
• scientific article; zbMATH DE number 1974122

Cites work

• scientific article; zbMATH DE number 1189242 (Why is no real title available?)
• scientific article; zbMATH DE number 1974122 (Why is no real title available?)
• A new perspective on clustered planarity as a combinatorial embedding problem
• C-Planarity of C-Connected Clustered Graphs
• Clustered Planarity: Clusters with Few Outgoing Edges
• Clustered Planarity: Embedded Clustered Graphs with Two-Component Clusters
• Clustered planarity: small clusters in cycles and Eulerian graphs
• Clustering Cycles into Cycles of Clusters
• Completely connected clustered graphs
• Computing Maximum C-Planar Subgraphs
• Efficient \(C\)-planarity testing for embedded flat clustered graphs with small faces
• Graph Drawing
• Graph clustering
• Noncrossing Subgraphs in Topological Layouts
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• On the computational complexity of upward and rectilinear planarity testing
• Overlapping Cluster Planarity
• Planarity for clustered graphs
• Relaxing the constraints of clustered planarity
• Shrinking the search space for clustered planarity
• Splitting clusters to get c-planarity
• Testing Planarity of Partially Embedded Graphs
• Toward a theory of planarity: Hanani-Tutte and planarity variants
• Upward drawings of triconnected digraphs.

Cited in

(7)

• Efficient C-Planarity Testing for Embedded Flat Clustered Graphs with Small Faces
• Efficient \(C\)-planarity testing for embedded flat clustered graphs with small faces
• Beyond Clustered Planar Graphs
• C-planarity testing of embedded clustered graphs with bounded dual carving-width
• A new perspective on clustered planarity as a combinatorial embedding problem
• Embedding graphs into embedded graphs
• Atomic embeddability, clustered planarity, and thickenability

This page was built for publication: Advances on testing C-planarity of embedded flat clustered graphs

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