An algorithm for constructing star-shaped drawings of plane graphs |
| |
Authors: | Seok-Hee Hong Hiroshi Nagamochi |
| |
Affiliation: | aSchool of Information Technologies, University of Sydney, Australia;bDepartment of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Japan |
| |
Abstract: | 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. |
| |
Keywords: | Graph drawing Convex drawing Star-shaped drawing Plane graphs Biconnected plane graphs Concave corner |
本文献已被 ScienceDirect 等数据库收录! |
|