Convex Drawings of Plane Graphs of Minimum Outer Apices

Miura, 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 12-14, 2005 , pp. 297-308(Official URL: http://dx.doi.org/10.1007/11618058_27).

Full text not available from this repository.

Abstract

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.

Item Type: Conference Paper
Additional Information: 10.1007/11618058_27
Classifications: M Methods > M.600 Planar
P Styles > P.720 Straight-line
P Styles > P.540 Planar
URI: http://gdea.informatik.uni-koeln.de/id/eprint/699

Actions (login required)

View Item View Item