Relaxing the constraints of clustered planarity

DOI10.1016/j.comgeo.2014.08.001zbMath1315.65015arXiv1207.3934OpenAlexW2039535226WikidataQ62046555 ScholiaQ62046555MaRDI QIDQ2261574

Giuseppe Di Battista, Giordano Da Lozzo, Maurizio Patrignani, Patrizio Angelini, Fabrizio Frati, Vincenzo Roselli

Publication date: 6 March 2015

Published in: Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

complexityalgorithmplanar graphsgraph drawingNP-hardnessclustered planarityclustered graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Complexity and performance of numerical algorithms (65Y20)

Related Items

Advances on Testing C-Planarity of Embedded Flat Clustered Graphs, Computing NodeTrix Representations of Clustered Graphs, Clustered planarity = flat clustered planarity, C-planarity testing of embedded clustered graphs with bounded dual carving-width, Beyond Clustered Planar Graphs, Advancements on SEFE and partitioned book embedding problems

Cites Work

• Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph
• On simultaneous planar graph embeddings
• On embedding a cycle in a plane graph
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Which crossing number is it anyway?
• On-line maintenance of triconnected components with SPQR-trees
• Completely connected clustered graphs
• Crossing Number is NP-Complete
• Efficient C-Planarity Testing for Embedded Flat Clustered Graphs with Small Faces
• Splitting Clusters to Get C-Planarity
• Clustered Planarity: Clusters with Few Outgoing Edges
• Clustered Planarity: Embedded Clustered Graphs with Two-Component Clusters
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• On-Line Planarity Testing
• Simultaneous Embedding of Planar Graphs with Few Bends
• Clustering Cycles into Cycles of Clusters
• C-Planarity of C-Connected Clustered Graphs
• Clustered Planarity: Small Clusters in Eulerian Graphs
• Simultaneous Embedding with Two Bends per Edge in Polynomial Area
• Graph Drawing
• Planarity for clustered graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item