Star-shaped Graph Drawing


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 real-world 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 non-convex drawings, called "star-shaped 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 real-world networks.


S. Hong and H. Nagamochi, "A Linear Time Algorithm for Constructing a Star-shaped Drawing of Planar Graphs with the Minimum Number of Concave Corners", Algorithmica, 62(3-4), pp. 1122-1158, 2012.

A star-shaped drawing of a graph is a straight-line drawing such that each inner facial cycle is drawn as a star-shaped polygon, and the outer facial cycle is drawn as a convex polygon. In this paper, we consider the problem of finding a star-shaped 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 linear-time 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 star-shaped drawings of plane graphs with a fixed embedding and concave corner constraints", Theoretical Computer Science, 2012.

A star-shaped drawing of a plane graph is a straight-line drawing such that each inner facial cycle is drawn as a star-shaped 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 star-shaped drawings. First, we consider the problem of finding a star-shaped 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 star-shaped 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 linear-time testing algorithm to test such conditions. Next, given a non-negative cost for each corner in G, we show that a star-shaped drawing D of G with the minimum cost can be found in linear-time, 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 Star-shaped Drawing of Planar Graphs", Computational Geometry: Theory and Applications, Volume 43, Issue 2, February 2010, pp. 191-206, 2010, Elsevier.

A straight-line 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 well-established 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 star-shaped drawing of a plane graph as a straight-line planar drawing such that each inner facial cycle is drawn as a star-shaped polygon, and the outer facial cycle is drawn as a convex polygon. A star-shaped 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 star-shaped drawing whose concave corners are given by the corners in A, and present a linear time algorithm for constructing such a star-shaped drawing.