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 , 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

Actions (login required)

View Item View Item