C-Planarity of Extrovert Clustered Graphs

Goodrich, Michael T. and Lueker, George S. and Sun, Jonathan Z. (2006) C-Planarity of Extrovert Clustered Graphs. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005 , pp. 211-222(Official URL: http://dx.doi.org/10.1007/11618058_20).

Full text not available from this repository.


A clustered graph has its vertices grouped into clusters in a hierarchical way via subset inclusion, thereby imposing a tree structure on the clustering relationship. The c-planarity problem is to determine if such a graph can be drawn in a planar way, with clusters drawn as nested regions and with each edge (drawn as a curve between vertex points) crossing the boundary of each region at most once. Unfortunately, as with the graph isomorphism problem, it is open as to whether the c-planarity problem is NP-complete or in P. In this paper, we show how to solve the c-planarity problem in polynomial time for a new class of clustered graphs, which we call emph{extrovert} clustered graphs. This class is quite natural (we argue that it captures many clustering relationships that are likely to arise in practice) and includes the clustered graphs tested in previous work by Dahlhaus as well as Feng, Eades, and Cohen. Interestingly, this class of graphs does not include, nor is it included by, a class studied recently by Gutwenger extit{et al.}, therefore, this paper offers a alternative advancement in our understanding of the efficient drawability of clustered graphs in a planar way. Our testing algorithm runs in O(n^3) time, implies an embedding algorithm with the same time complexity, and can be easily implemented.

Item Type: Conference Paper
Additional Information: 10.1007/11618058_20
Classifications: P Styles > P.180 Cluster
G Algorithms and Complexity > G.770 Planarity Testing
URI: http://gdea.informatik.uni-koeln.de/id/eprint/718

Actions (login required)

View Item View Item