Department of Applied Mathematics & Physics, Kyoto University
Technical Report 2007-004 (January 28, 2007)
Convex Drawings of Hierarchical Planar Graphs and Clustered Planar Graphs
by Seok-Hee Hong and Hiroshi Nagamochi
Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures. Both have applications in VLSI design, CASE tools, software visualisation and visualisation of social networks and biological networks. Straight-line drawing algorithms for hierarchical graphs and clustered graphs
have been presented in [P. Eades, Q. Feng, X. Lin and H. Nagamochi, Straight-line drawing algorithms for hierarchical graphs and clustered graphs, Algorithmica, 44, pp. 1-32, 2006].
A straight-line drawing is called a convex drawing if every
facial cycle is drawn as a convex polygon. In this paper, it is proved that every internally triconnected hierarchical plane graph with the outer facial cycle drawn as a convex polygon admits a convex drawing. We present an algorithm which constructs such a drawing.
We then extend our results to convex representations of clustered planar graphs. It is proved that every internally triconnected clustered plane graph with completely connected clustering structure admits a convex drawing. We present an algorithm to construct a convex drawing of clustered planar graphs.