Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2008-002 (March 22, 2008)

Star-shaped Drawings of Graphs with Fixed Embedding and Concave Corner Constraints
by Seok-Hee Hong, Hiroshi Nagamochi

pdf File

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, given a biconnected planar graph $G$ with fixed plane embedding and a subset $A$ of corners of $G$, we consider the problem of finding a star-shaped drawing $D$ of $G$ such that only corners in $A$ are allowed to become concave corners in $D$. We first characterize a necessary and sufficient condition for a subset $A$ of corners to admit such a star-shaped drawing $D$. Then we present a linear time algorithm for finding such a star-shaped drawing $D$. Our characterization includes Thomassen