Planarity-Preserving Clustering and Embedding for Large Planar Graphs

Duncan, Christian A. and Goodrich, Michael T. and Kobourov, Stephen G. (1999) Planarity-Preserving Clustering and Embedding for Large Planar Graphs. In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999, Štirín Castle, Czech Republic , pp. 186-196 (Official URL:

Full text not available from this repository.


In this paper we present a novel approach for cluster-based drawing of large planar graphs that maintains planarity. Our technique works for arbitrary planar graphs and produces a clustering which satisfies the conditions for compound-planarity (c-planarity). Using the clustering, we obtain a representation of the graph as a collection of O(log n) layers, where each succeeding layer represents the graph in an increasing level of detail. At the same time, the difference between two graphs on neighboring layers of the hierarchy is small, thus preserving the viewer's mental map. The overall running time of the algorithm is O(n log n), where n is the number of vertices of graph G.

Item Type:Conference Paper
Additional Information:10.1007/3-540-46648-7_19
Classifications:G Algorithms and Complexity > G.490 Embeddings
P Styles > P.180 Cluster
M Methods > M.600 Planar
G Algorithms and Complexity > G.350 Clusters
P Styles > P.540 Planar
ID Code:327

Repository Staff Only: item control page


C. A. Duncan, M. T. Goodrich, and S. G. Kobourov. Balanced aspect ratio trees and their use for drawing very large graphs. Proc. of 6th Symposium on Graph Drawing (GD'98), LNCS 1190:101-112, 1998.

P. Eades and Q. W. Feng. Multilevel visualization of clustered graphs. Proc. of 4th Symposium on Graph Drawing (GD'96), LNCS 1190:101-112, 1996.

P. Eades and Q. W. Feng, and X. Lin. Straight-line drawing algorithms for hierarchical graphs and clustered graphs. Proc. of the 4th Symposium on Graph Drawing (GD'96), LNCS 1190:113-128, 1997.

I. Fary. On straight lines representation of planar graphs. Acta Sci. Math. Szeged, 11:229-233, 1948.

Q.-W. Feng, R. F. Cohen, and P. Eades. Planarity for clustered graphs. ESA '95, LNCS 979:213-226, 1995.

R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM J. Appl. Math., 36:177-189, 1979.

F. J. Newbery. Edge concentration: A method for clustering directed graphs. In Proceedings of the 2nd International Workshop on Software Configuration Management, pages 76-85, Princeton, New Jersey, October 1989.

S. C. North. Drawing ranked digraphs with recursive clusters. ALCOM International Workshop PARIS 1993 on Graph Drawing and Topological Graph Algorithms (GD'93), September 1993.

Sablowski and Frick. Automatic graph clustering. Proc. of 4th Symposium on Graph Drawing (GD'96), LNCS 1190:395-400, 1996.

W. Schnyder. Embedding planar graphs on the grid. In Proc. 1st ACM-SIAM Sympos. Discrete Algorithms, pages 138-148, 1990.

K. Sugiyama and K. Misue. Visualization of structural information: Automatic drawing of compound digraphs. IEEE Trans. Softw. Eng., 21(4):876-892, 1991.

K. Wagner. Bemerkungen zum Vierfarbenproblem. Jahresbericht der Deutschen Mathematiker-Vereinigung, 46:26-32, 1936.