Drawing Clustered Graphs on an Orthogonal Grid

Eades, Peter and Feng, Qing-Wen (1998) Drawing Clustered Graphs on an Orthogonal Grid. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997 , pp. 146-157(Official URL: http://dx.doi.org/10.1007/3-540-63938-1_58).

Full text not available from this repository.


Clustered graphs are graphs with recursive clustering structures over the vertices. For graphical representation, the clustering structure is represented by a simple region that contains the drawing of all the vertices which belong to that cluster. In this paper, we present an algorithm which produces planar drawings of clustered graphs in a convention known as orthogonal grid rectangular cluster drawings. We present an algorithm which produces such drawings with O(n²) area and with at most 3 bends in each edge. This result is as good as existing results of planar graphs. Further, we show that our algorithm is optimal in terms of the number of bends in each edge.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-63938-1_58
Classifications: P Styles > P.900 Visibility
P Styles > P.180 Cluster
G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
URI: http://gdea.informatik.uni-koeln.de/id/eprint/75

Actions (login required)

View Item View Item