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, we consider the problem of finding a star‐shaped drawing of a biconnected planar graph with the minimum number of concave corners. We first show new structural properties of planar graphs to derive a lower bound on the number of concave corners. Based on the lower bound, we prove that the problem can be solved in linear time by presenting a linear‐time algorithm for finding a best plane embedding of a biconnected planar graph with the minimum number of concave corners. This is in spite of the fact that a biconnected planar graph may have an exponential number of different plane embeddings.
