A Linear-Time Algorithm for Star-Shaped Drawings of Planar Graphs with the Minimum Number of Concave Corners |
| |
Authors: | Seok-Hee Hong Hiroshi Nagamochi |
| |
Affiliation: | 1. School of Information Technologies, University of Sydney, Sydney, Australia 2. Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Kyoto, Japan
|
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|