An algorithm for constructing star-shaped drawings of plane graphs

作者：Hong Seok Hee^*; Nagamochi Hiroshi

来源：Computational Geometry-Theory and Applications, 2010, 43(2): 191-206.

DOI：10.1016/j.comgeo.2009.06.008

• Graph drawing
• Convex drawing
• Star-shaped drawing
• Plane graphs
• Biconnected plane graphs
• Concave corner

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. Thornassen [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.

• 出版日期2010-2