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, Limerick, Ireland , 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
ID Code:699

Repository Staff Only: item control page

References

N. Chiba, T. Yamanouchi and T. Nishizeki.: Linear algorithms for convex drawings of planar graphs. Progress in Graph Theory, J. A. Bondy and U. S. R. Murty (Eds.), Academic Press, pp. 153-173 (1984).

M. Chrobak and G. Kant.: Convex grid drawings of 3-connected planar graphs. International Journal of Computational Geometry and Applications, 7, pp. 211-223 (1997).

H. de Fraysseix, J. Pach and R. Pollack.: How to draw a planar graph on a grid. Combinatorica, 10, pp. 41-51 (1990).

G. Di Battista, P. Eades, R. Tamassia and I. G. Tollis.: Graph Drawing, Prentice Hall, NJ (1999).

J. E. Hopcroft and R. E. Tarjan.: Dividing a graph into triconnected components, SIAM J. Compt., 2, 3, pp. 135-138 (1973).

K. Miura, M. Azuma and T. Nishizeki.: Canonical decomposition, realizer, Schnyder labeling and orderly spanning trees of plane graphs, International Journal of Fundations of Computer Science, 16, 1, pp. 117-141 (2005).

T. Nishizeki and Md. S. Rahman.: Planar Graph Drawing, World Scientific, Singapore (2004).

W. Schnyder: Embedding planar graphs on the grid. Proc. 1st Annual ACM-SIAM Symp. on Discrete Algorithms, San Francisco, pp. 138-147 (1990).

C. Thomassen.: Plane representations of graphs, in Progress in Graph Theory J. A. Bondy and U. S. R. Murty (Eds.), Academic Press, pp. 43--69