Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2007-003 (January 28, 2007)

Convex Drawings of Graphs with Non-convex Boundary Constraints
by Seok-Hee Hong and Hiroshi Nagamochi

pdf File

In this paper, we study a new problem of convex drawing of planar graphs with non-convex boundary constraints. It is proved that every triconnected plane graph whose boundary is fixed with a star-shaped polygon admits a drawing in which every inner facial cycle is drawn as a convex polygon. We also prove that every four-connected plane graph whose boundary is fixed with a crown-shaped polygon admits such a drawing, called an inner-convex drawing. We present an algorithm to construct an inner-convex drawing in linear time.