2015/06/18 by Thomas Bläsius, Ignaz Rutter, Bläsius, Thomas +1
Computer Science · Social Sciences · #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #G.2.2 #Geographic Information Systems Studies #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1506.05673
openalex publication_date 2015/06/18 · openalex created_date 2022/09/29 · openalex updated_date 2026/07/28
The clustered planarity problem (c-planarity) asks whether a hierarchically\nclustered graph admits a planar drawing such that the clusters can be nicely\nrepresented by regions. We introduce the cd-tree data structure and give a new\ncharacterization of c-planarity. It leads to efficient algorithms for\nc-planarity testing in the following cases. (i) Every cluster and every\nco-cluster (complement of a cluster) has at most two connected components. (ii)\nEvery cluster has at most five outgoing edges.\n Moreover, the cd-tree reveals interesting connections between c-planarity and\nplanarity with constraints on the order of edges around vertices. On one hand,\nthis gives rise to a bunch of new open problems related to c-planarity, on the\nother hand it provides a new perspective on previous results.\n