Convex Drawings of Plane Graphs of Minimum Outer Apices

摘要

In a convex drawing of a plane graph G, every facial cycle of G is drawn as a convex polygon. A polygon for the outer facial cycle is called an outer convex polygon. A necessary and sufficient condition for a plane graph G to have a convex drawing is known. However, it has not been known how many apices of an outer convex polygon are necessary for G to have a convex drawing. In this paper, we show that the minimum number of apices of an outer convex polygon necessary for G to have a convex drawing is, in effect, equal to the number of leaves in a triconnected component decomposition tree of a new graph constructed from G, and that a convex drawing of G having the minimum number of apices can be found in linear time.