S. Hong and H. Nagamochi, "Linear time algorithm for Symmetric Convex Drawings of Planar Graphs", to appear Algorithmica, Springer, Volume 58, Number 2, pp. 433460, 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 straightline 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 lineartime 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):304320, 1960; Proc. Lond. Math. Soc. 13:743768, 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:346358, 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 angleconstrained 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 angleconstrained convex drawing of plane graphs, where some of outer vertices have angle constraints.
Our results also imply that there is a lineartime algorithm that constructs maximally symmetric convex drawings of triconnected planar graphs. Previous algorithm (Hong et al. in Discrete Comput. Geom. 36:283311, 2006) constructs symmetric drawings of triconnected planar graphs with straightlines.

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 straightline 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. 4369] 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 straightline 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 Nonconvex Boundary Constraints", Discrete Applied Mathematics, 156(12), pp. 23682380, Elsevier, 2008.
In this paper, we study a new problem of convex drawing of planar graphs with nonconvex boundary constraints, and call a drawing in which every innerfacial cycle is drawn as a convex polygon an innerconvex drawing. It is proved that every triconnected plane graph with the boundary fixed with a starshaped polygon whose kernel has a positive area admits an innerconvex drawing. We also prove that every fourconnected plane graph whose boundary is fixed with a crownshaped polygon admits an innerconvex drawing. We present linear time algorithms to construct innerconvex drawings for both cases.
