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

Abstract: 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 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 of such that only prescribed corners are allowed to become concave corners in . More specifically, we characterize a necessary and sufficient condition for a subset of prescribed corners to admit such a star-shaped drawing of . Our characterization includes Thomassen’s characterization of biconnected plane graphs with a prescribed boundary that have convex drawings . We also give a linear-time testing algorithm to test such conditions. Next, given a non-negative cost for each corner in , we show that a star-shaped drawing of 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. [Copyright &y& Elsevier]