A New Perspective on Clustered Planarity as a Combinatorial Embedding ProblemBläsius, Thomas and Rutter, Ignaz (2014) A New Perspective on Clustered Planarity as a Combinatorial Embedding Problem. In: Graph Drawing 22nd International Symposium, GD 2014, September 2426, 2014 , pp. 440451(Official URL: http://dx.doi.org/10.1007/9783662458037_37). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783662458037_37
AbstractThe clustered planarity problem (cplanarity) asks whether a hierarchically clustered graph admits a planar drawing such that the clusters can be nicely represented by regions. We introduce the cdtree data structure and give a new characterization of cplanarity. It leads to efficient algorithms for cplanarity testing in the following cases. (i) Every cluster and every cocluster has at most two connected components. (ii) Every cluster has at most five outgoing edges. Moreover, the cdtree reveals interesting connections between cplanarity and planarity with constraints on the order of edges around vertices. On one hand, this gives rise to a bunch of new open problems related to cplanarity, on the other hand it provides a new perspective on previous results.
Actions (login required)
