A new perspective on clustered planarity as a combinatorial embedding problem

DOI10.1016/j.tcs.2015.10.011zbMath1331.68242arXiv1506.05673OpenAlexW1805816469MaRDI QIDQ897898

Ignaz Rutter, Thomas Bläsius

Publication date: 8 December 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

algorithmscharacterizationgraph drawingclustered planarityconstrained planar embedding

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Advances on Testing C-Planarity of Embedded Flat Clustered Graphs, Clustered planarity with pipes, Synchronized Planarity with Applications to Constrained Planarity Problems, Hanani-Tutte for Radial Planarity II, Beyond Level Planarity, Simultaneous Orthogonal Planarity, Embedding graphs into embedded graphs, Parameterized complexity of graph planarity with restricted cyclic orders, Clustered planarity = flat clustered planarity, Simultaneous embedding: edge orderings, relative positions, cutvertices, Parameterized complexity of graph planarity with restricted cyclic orders, C-planarity testing of embedded clustered graphs with bounded dual carving-width, Drawing Clustered Planar Graphs on Disk Arrangements, Beyond Clustered Planar Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On embedding a cycle in a plane graph
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On-line maintenance of triconnected components with SPQR-trees
• Completely connected clustered graphs
• Simpler Algorithms for Testing Two-Page Book Embedding of Partitioned Graphs
• Advances on Testing C-Planarity of Embedded Flat Clustered Graphs
• Efficient C-Planarity Testing for Embedded Flat Clustered Graphs with Small Faces
• Clustered Planarity: Small Clusters in Cycles and Eulerian Graphs
• Clustered Planarity: Clusters with Few Outgoing Edges
• Clustered Planarity: Embedded Clustered Graphs with Two-Component Clusters
• Hierarchical planarity testing algorithms
• Shrinking the Search Space for Clustered Planarity
• Clustering Cycles into Cycles of Clusters
• C-Planarity of C-Connected Clustered Graphs
• Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems
• Graph Drawing
• Planarity for clustered graphs