S. Hong and H. Nagamochi, "Linear time algorithm for Symmetric Convex Drawings of Planar Graphs", to appear Algorithmica, Springer, Volume 58, Number 2, pp. 433-460, 2010

Symmetry is one of the most important aesthetic criteria in Graph Drawing which can reveal the hidden structure in the graph. Convex drawing is a straight-line drawing where every facial cycle is drawn as a convex polygon.
In this paper, we prove that given an internally triconnected plane graph with symmetries, there exists a convex drawing of the graph which displays the given symmetries. We present a linear-time algorithm for constructing symmetric convex drawings of internally triconnected planar graphs.
This is an extension of a classical result due to Tutte (Proc. Lond. Math. Soc. 10(3):304-320, 1960; Proc. Lond. Math. Soc. 13:743-768, 1963) who proved that every triconnected plane graph with a given convex polygon as a boundary admits a convex drawing. Note that Tutte's barycenter mapping method can be implemented in O(n 1.5) time and O(nlog n) space at best (Lipton et al. in SIAM J. Numer. Anal. 16:346-358, 1979).
Our divide and conquer algorithm explicitly exploits the fundamental properties of symmetric drawing, which consists of congruent drawings of isomorphic subgraphs. We first find an isomorphic subgraph of a given symmetric plane graph, and compute an angle-constrained convex drawing of the subgraph. Finally, a symmetric convex drawing of the given graph is constructed by merging repetitive copies of the congruent drawings of isomorphic subgraphs. For this purpose, we define a new problem of angle-constrained convex drawing of plane graphs, where some of outer vertices have angle constraints.
Our results also imply that there is a linear-time algorithm that constructs maximally symmetric convex drawings of triconnected planar graphs. Previous algorithm (Hong et al. in Discrete Comput. Geom. 36:283-311, 2006) constructs symmetric drawings of triconnected planar graphs with straight-lines.

 

S. Hong and H. Nagamochi, "Convex Drawings of Hierarchical Planar Graphs and Clustered Planar Graphs", Journal of Discrete Algorithm, Elsevier, 8(3), pp. 282 - 295, 2010.

In this paper, we present results on convex drawings of hierarchical graphs and clustered graphs. A convex drawing is a planar straight-line drawing of a plane graph, where every facial cycle is drawn as a convex polygon. Hierarchical graphs and clustered graphs are useful graph models with structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures.
We first present the necessary and sufficient conditions for a hierarchical plane graph to admit a convex drawing. More specifically, we show that the necessary and sufficient conditions for a biconnected plane graph due to Thomassen [C. Thomassen, Plane representations of graphs, in: J.A. Bondy, U.S.R. Murty (Eds.), Progress in Graph Theory, Academic Press, 1984, pp. 43-69] remains valid for the case of a hierarchical plane graph. We then prove that every internally triconnected clustered plane graph with a completely connected clustering structure admits a "fully convex drawing," a planar straight-line drawing such that both clusters and facial cycles are drawn as convex polygons. We also present algorithms to construct such convex drawings of hierarchical graphs and clustered graphs.

      

S. Hong and H. Nagamochi, "Convex Drawings of Graphs with Non-convex Boundary Constraints", Discrete Applied Mathematics, 156(12), pp. 2368-2380, Elsevier, 2008.

In this paper, we study a new problem of convex drawing of planar graphs with non-convex boundary constraints, and call a drawing in which every inner-facial cycle is drawn as a convex polygon an inner-convex drawing. It is proved that every triconnected plane graph with the boundary fixed with a star-shaped polygon whose kernel has a positive area admits an inner-convex drawing. We also prove that every four-connected plane graph whose boundary is fixed with a crown-shaped polygon admits an inner-convex drawing. We present linear time algorithms to construct inner-convex drawings for both cases.