Straight-Line Drawing Algorithms for Hierarchical Graphs and Clustered Graphs

Eades, Peter and Feng, Qing-Wen and Lin, Xuemin (1997) Straight-Line Drawing Algorithms for Hierarchical Graphs and Clustered Graphs. In: Symposium on Graph Drawing, GD '96, September 18-20, 1996, Berkeley, California, USA , pp. 113-128 (Official URL:

Full text not available from this repository.


Hierarchical graphs and clustered graphs are useful nonclassical graph models for structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures. Both have applications in CASE tools, software visualization, VLSI design, etc. Drawing algorithms for hierarchical graphs have been well investigated. However, the problem of straight-line representation has not been addressed. In this paper, we answer the question: does every planar hierarchical graph admit a planar straight-line hierarchical drawing? We present an algorithm that constructs such drawings in O(n²) time. Also, we answer a basic question for clustered graphs, i.e. does every planar clustered graph admit a planar straight-line drawing with clusters drawn as convex polygons? A method for such drawings is provided in this paper.

Item Type:Conference Paper
Additional Information:10.1007/3-540-62495-3_42
Classifications:M Methods > M.500 Layered
P Styles > P.720 Straight-line
P Styles > P.180 Cluster
P Styles > P.480 Layered
G Algorithms and Complexity > G.350 Clusters
ID Code:107

Repository Staff Only: item control page


G. Di Battista and R. Tamassia. Algorithms for plane representations of acyclic digraphs. Theoretical Computer Science, 61:175-198, 1988.

J.A. Bondy and U.S.R. Murty. Graph Theory with Applications. North-Holland, New-York, N.Y., 1976.

P. Eades and K. Sugiyama. How to draw a directed graph. Journal of Information Processing, 424-437, 1991.

Peter Eades and Qing-Wen Feng. Orthogonal grid drawing of clustered graphs. Technical Report 96-04, Department of Computer Science, The University of Newcastle, Australia, 1996.

Peter Eades, Xuemin Lin, and Roberto Tamassia. An algorithm for drawing a hierarchical graph. Internat. Jour. of Comput. Geom. and Appl., 1995.

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

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

Qing-Wen Feng, Robert F. Cohen, and Peter Eades. How to draw a planar clustered graph. In COCOON '95, volume 959 of LNCS, pages 21-31. Springer-Verlag, 1995.

Qing-Wen Feng, Robert F. Cohen, and Peter Eades. Planarity for clustered graphs. In ESA '95, volume 979 of LNCS, pages 213-226. Springer-Verlag, 1995.

E.R. Gansner, S.C. North, and K. P. Vo. DAG - A program that draws directed graphs. Softw. - Pract. Exp., 18(11):1047-1062, 1988.

D. Harel. On visual formalisms. Communications of the ACM, 31(5):514-530, 1988.

Wei Lai. Building Interactive Digram Applications. PhD thesis, Department of Computer Science, University of Newcastle, Australia, 2308, June 1993.

Thomas Lengauer. Hierarchical planarity testing algorithms. Journal of the ACM, 36:475-509, 1989.

Xuemin Lin. Analysis of algorithms for drawing graphs. PhD thesis, Department of Computer Science, University of Queensland, Australia, 1992.

Franco P. Preparata and Michael I. Shamos. Computational geometry: an introduction. Springer-Verlag, New-York, 1985.

R. Read. Methods for computer display and manipulation of graphs and the corresponding algorithms. Technical Report 86-12, Faculty of Mathematics, Univ. of Waterloo, July 1986.

S.K. Stein. Convex maps. Proceedings American Mathematical Society, 2:464-466, 1951.

K. Sugiyama and K. Misue. Visualization of structural information: Automatic drawing of compound digraphs. IEEE Transactions on Systems, Man and Cybernetics, 21(4):876-892, 1991.

K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical systems. IEEE Trans. Syst. Man. Cybern., SMC-11(2):109-125, 1981.

W.T. Tutte. How to draw a graph. Proceedings of the London Mathematical Society, 3(13):743-768, 1963.

K. Wagner. Bemerkungen zum vierfarben problem. Jber. Deutsch. Math.-Verein,46:26-32, 1936.