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 ⌈n/2⌉-1 and height ⌈n/2⌉ 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 ⌈n/2⌉ - 1 and height ⌈n/⌉e.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
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, T. 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).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Miura, K., Nakano, Si., Nishizeki, T. (1999). Grid Drawings of Four-Connected Plane Graphs. In: Kratochvíyl, J. (eds) Graph Drawing. GD 1999. Lecture Notes in Computer Science, vol 1731. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46648-7_15
Download citation
DOI: https://doi.org/10.1007/3-540-46648-7_15
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66904-3
Online ISBN: 978-3-540-46648-2
eBook Packages: Springer Book Archive