The very first paper on graph drawing was by Tutte in 1960, on convex representations; convexity is a
desirable property for graph visualisations in aesthetic and mathematical terms. However, Tutte's
method has a strong "triconnectivity" constraint. Unfortunately, most graphs arising from realworld
applications are biconnected, for which convex representations are not possible, I showed that it is
possible to approximate convexity with the weaker constraint of biconnectivity.
My paper initiated a new direction on "almost"convex representations of graphs, by introducing new
aesthetic criteria for nonconvex drawings, called "starshaped drawings", which minimise the
number of "concave corners" in a drawing. I provided the first optimal algorithm to construct these
drawings of biconnected graphs which can be used to visualise a much broader class of realworld
networks. 
S. Hong and H. Nagamochi, "A Linear Time Algorithm for Constructing a Starshaped Drawing of Planar Graphs with the Minimum Number of Concave Corners", Algorithmica, 62(34), pp. 11221158, 2012.
A starshaped drawing of a graph is a straightline drawing such that each inner facial cycle is drawn as a starshaped polygon, and the outer facial cycle is drawn as a convex polygon. In this paper, we consider the problem of finding a starshaped drawing of a biconnected planar graph with the minimum number of concave corners. We first show new structural properties of planar graphs to derive a lower bound on the number of concave corners. Based on the lower bound, we prove that the problem can be solved in linear time by presenting a lineartime algorithm for finding a best plane embedding of a biconnected planar graph with the minimum number of concave corners. This is in spite of the fact that a biconnected planar graph may have an exponential number of different plane embeddings.

S. Hong and H. Nagamochi, "Minimum cost starshaped drawings of plane graphs with a fixed embedding and concave corner constraints", Theoretical Computer Science, 2012.
A starshaped drawing of a plane graph is a straightline drawing such that each inner facial cycle is drawn as a starshaped polygon, and the outer facial cycle is drawn as a convex polygon. In this paper, given a biconnected plane graph G with fixed plane embedding and a prescribed set of concave corners, we study the following two problems on starshaped drawings. First, we consider the problem of finding a starshaped drawing D of G such that only prescribed corners are allowed to become concave corners in D. More specifically, we characterize a necessary and sufficient condition for a subset of prescribed corners to admit such a starshaped drawing D of G. Our characterization includes Thomassen's characterization of biconnected plane graphs with a prescribed boundary that have convex drawings Thomassen (1984). We also give a lineartime testing algorithm to test such conditions. Next, given a nonnegative cost for each corner in G, we show that a starshaped drawing D of G with the minimum cost can be found in lineartime, where the cost of a drawing is defined by the sum of costs of concave corners in the drawing.

S. Hong and H. Nagamochi, "An Algorithm for Constructing Starshaped Drawing of Planar Graphs", Computational Geometry: Theory and Applications, Volume 43, Issue 2, February 2010, pp. 191206, 2010, Elsevier.
A straightline planar drawing of a plane graph is called a convex drawing if every facial cycle is drawn as a convex polygon. Convex drawings of graphs is a wellestablished aesthetic in graph drawing, however not all planar graphs admit a convex drawing. Tutte [W.T. Tutte, Convex representations of graphs, Proc. of London Math. Soc. 10 (3) (1960) 304–320] showed that every triconnected plane graph admits a convex drawing for any given boundary drawn as a convex polygon. Thomassen [C. Thomassen, Plane representations of graphs, in: Progress in Graph Theory, Academic Press, 1984, pp. 43–69] gave a necessary and sufficient condition for a biconnected plane graph with a prescribed convex boundary to have a convex drawing.
In this paper, we initiate a new notion of starshaped drawing of a plane graph as a straightline planar drawing such that each inner facial cycle is drawn as a starshaped polygon, and the outer facial cycle is drawn as a convex polygon. A starshaped drawing is a natural extension of a convex drawing, and a new aesthetic criteria for drawing planar graphs in a convex way as much as possible. We give a sufficient condition for a given set A of corners of a plane graph to admit a starshaped drawing whose concave corners are given by the corners in A, and present a linear time algorithm for constructing such a starshaped drawing.
