Convex Drawings of Plane Graphs of Minimum Outer ApicesMiura, Kazuyuki and Azuma, Machiko and Nishizeki, Takao (2006) Convex Drawings of Plane Graphs of Minimum Outer Apices. In: Graph Drawing 13th International Symposium, GD 2005, September 1214, 2005 , pp. 297308(Official URL: http://dx.doi.org/10.1007/11618058_27). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/11618058_27
AbstractIn 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.
Actions (login required)
