Grid Drawings of Four-Connected Plane Graphs

Miura, Kazuyuki and Nakano, Shin-Ichi and Nishizeki, Takao (1999) Grid Drawings of Four-Connected Plane Graphs. In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999, Štirín Castle, Czech Republic , pp. 145-154 (Official URL: http://dx.doi.org/10.1007/3-540-46648-7_15).

Full text not available from this repository.

Abstract

A grid drawing of a plane graph G is a drawing of G on the plane so that all vertices of G are put on plane grid points and all edges are drawn as straight line segments between their endpoints without any edge-intersection. In this paper we give a very simple algorithm to find a grid drawing of any given 4-connected plane graph G with four or more vertices on the outer face. The algorithm takes time O(n) and needs a rectangular grid of width \lceil n/2 \rceil - 1 and height \lceil n/2 \rceil if G has n vertices. The algorithm is best possible in the sense that there are an infinite number of 4-connected plane graphs any grid drawings of which need rectangular grids of width \lceil n/2 \rceil - 1 and height \lceil n/2 \rceil.

Item Type:Conference Paper
Additional Information:10.1007/3-540-46648-7_15
Classifications:P Styles > P.720 Straight-line
G Algorithms and Complexity > G.070 Area / Edge Length
M Methods > M.600 Planar
P Styles > P.999 Others
P Styles > P.540 Planar
ID Code:304

Repository Staff Only: item control page

References

G. Di Battista, P. Eades, R. Tamassia and I. G. Tollis, Automatic graph drawing: an annotated bibliography, Computational Geometry: Theory and Applications, 4, 235-282 (1994).

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

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

M. Chrobak and S. Nakano, Minimum-width grid drawings of plane graphs, Computational Geometry: Theory and Applications, 10, 29-54 (1998).

N. Chiba, K. Onoguchi and T. Nishizeki, Drawing planar graphs nicely, Acta Informatica, 22, 187-201 (1985).

M. Chrobak and T. Payne, A linear-time algorithm for drawing planar graphs on a grid, Information Processing Letters, 54, 241-246 (1995).

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

I. Fáry, On straight lines representation of plane graphs, Acta. Sci. Math. Szeged, 11, 229-233 (1948).

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

X. He, Grid embedding of 4-connected plane graphs, Discrete & Computational Geometry, 17, 339-358 (1997).

G. Kant, Drawing planar graphs using the canonical ordering, Algorithmica, 16, 4-32 (1996).

G. Kant and X. He, Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems, Theoretical Computer Science, 172, 175-193 (1997).

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

S. K. Stein, Convex maps, Proc. Amer. Math. Soc., 2, 464-466 (1951).

W. T. Tutte, How to draw a graph, Proc. London Math. Soc., 13, 743-768 (1963).

K. Wagner, Bemerkungen zum Vierfarbenproblem, Jahresbericht der Deutschen Mathematiker-Vereinigung, 46, 26-32 (1936).