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, Limerick, Ireland , 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
ID Code:718

Repository Staff Only: item control page


G. D. Battista, W. Didimo, and A. Marcandalli. Planarization of clustered graphs. In Graph Drawing (GD'01), LNCS 2265, pages 60-74, 2001.

G. D. Battista and R. Tamassia. On-line planarity testing. SIAM J. Comput., 25(5):956-997, 1996.

K. Booth and G. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Systems Sci., 13(3):335-379, 1976.

P. G. Cortese, G. D. Battista, M. Patrignani, and M. Pizzonia. Clustering cycles into cycles of clusters. In Graph Drawing (GD'04), 2004.

E. Dahlhaus. A linear time algorithm to recognize clustered planar graphs and its parallelization. In LATIN'98, LNCS 1380, pages 239-248, 1998.

C. A. Duncan, M. T. Goodrich, and S. G. Kobourov. Planarity-preserving clustering and embedding for large planar graphs. In Graph Drawing (GD'99), LNCS 1731, pages 186-196, 1999.

P. Eades, Q. Feng, and H. Nagamochi. Drawing clustered graphs on an orthogonal grid. Journal of Graph Algorithms and Applications, 3(4):3-29, 1999.

P. Eades and Q.-W. Feng. Multilevel visualization of clustered graphs. In Graph Drawing, GD'96, LNCS 1190, pages 101-112, 1996.

P. Eades, Q.-W. Feng, and X. Lin. Straight-line drawing algorithms for hierarchical graphs and clustered graphs. In Graph Drawing, GD'96, LNCS 1190, pages 113-128, 1996.

P. Eades and M. L. Huang. Navigating clustered graphs using force-directed methods. J. Graph Algorithms and Applications: Special Issue on Selected Papers from 1998 Symp. Graph Drawing, 4(3):157-181, 2000.

S. Even and R. E. Tarjan. Computing an st-numbering. Theoretical Computer Science, 2(3):339-344, 1976.

Q.-W. Feng, P. Eades, and R. F. Cohen. Clustered graphs and C-planarity. In 3rd Annual European Symposium on Algorithms (ESA'95), LNCS 979, pages 213-226, 1995.

C. Gutwenger, M. Jünger, S. Leipert, P. Mutzel, M. Percan, and R. Weiskircher. Advances in C-planarity testing of clustered graphs. In Graph Drawing (GD'02), LNCS 2528, pages 220-235, 2002.

J. Hopcroft and R. E. Tarjan. Efficient planarity testing. J. ACM, 21(4):549-568, 1974.

W. Hsu and R. M. McConnell. PC trees and circular-ones arrangements. Theoretical Computer Science, 296(1):59-74, 2003.

A. Lempel, S. Even, and I. Cederbaum. An algorithm for planarity testing of graphs. In Theory of graphs: International symposium, pages 215-232, 1966.

T. Nishizeki and N. Chiba. Planar Graphs: Theory and Algorithms, volume 32 of Ann. Discrete Math. North-Holland, Amsterdam, The Netherlands, 1988.