A Linear-Time Algorithm for Star-Shaped Drawings of Planar Graphs with the Minimum Number of Concave Corners

作者：Hong Seok Hee^*; Nagamochi Hiroshi

来源：Algorithmica, 2012, 62(3-4): 1122-1158.

DOI：10.1007/s00453-011-9513-6

• Graph drawing
• Star-shaped drawing
• Convex drawing
• Biconnected planar graphs
• Concave corner
• Star-shaped polygon

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.

• 出版日期2012-4