Minimum cost star-shaped drawings of plane graphs with a fixed embedding and concave corner constraints

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 [24]. 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.