Abstract
A convex grid drawing of a plane graph G is a drawing of G on the plane so that all vertices of G are put on grid points, all edges are drawn as straight-line segments between their endpoints without any edge-intersection, and every face boundary is a convex polygon. In this paper we give a linear-time algorithm for finding a convex grid drawing of any 4-connected plane graph G with four or more vertices on the outer face boundary. The algorithm yields a drawing in an integer grid such that W + H ≤ n - 1 if G has n vertices, where W is the width and H is the height of the grid. Thus the area W x H of the grid is at most ⌈(n-1)=2⌉ · ⌈(n-1)/2⌉. Our bounds on the grid sizes are optimal in the sense that there exist an infinite number of 4-connected plane graphs whose convex drawings need grids such that W + H = n-1 and W x H = ⌈(n - 1)/2⌉ · ⌈(n - 1)/2⌉.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
G. Di Battista, P. Eades, R. Tamassia and I.G. Tollis, Graph Drawing,Prentice Hall, NJ (1999).
M. Chrobak and G. Kant, Convex grid drawings of 3-connected planar gra-phs, 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 Inform., 22, 187–201 (1985).
M. Chrobak and T. Payne,A linear-time algorithm for drawing planargraphs on a grid, Information Processing Letters, 54, 241–246 (1995).
N. Chiba, T. Yamanouchi and T. Nishizeki, Linear algorithms for convexdrawings 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 agrid, Combinatorica, 10, 41–51 (1990).
X. He, Grid embedding of 4-connected plane graphs, Discrete & Computa-tional 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 andits applications in graph drawing problems, Theoretical Computer Science,172, 175–193 (1997).
K. Miura, S. Nakano and T. Nishizeki, Grid drawings of four-connectedplane graphs, Proc. Graph Drawing’99 (GD’99), LNCS 1731, 145–154 (1999).
S. Nakano, M. Saidur Rahman and T. Nishizeki,A linear time algorithm for four partitioning four-connected planar graphs, Information ProcessingLetters, 62, 315–322 (1997).
W. Schnyder, Embedding planar graphs in the grid, Proc. 1st Annual ACM-SIAM Symp. on Discrete Algorithms, San Francisco, 138–147 (1990).
W. Schnyder and W. Trotter, Convex drawings of planar graphs, Abstractsof the AMS, 13, 5, 92T-05-135 (1992).
W.T. Tutte, How to draw a graph, Proc. London Math. Soc., 13, 743–768(1963).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Miura, K., Nakano, Si., Nishizeki, T. (2000). Convex Grid Drawings of Four-Connected Plane Graphs. In: Goos, G., Hartmanis, J., van Leeuwen, J., Lee, D.T., Teng, SH. (eds) Algorithms and Computation. ISAAC 2000. Lecture Notes in Computer Science, vol 1969. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-40996-3_22
Download citation
DOI: https://doi.org/10.1007/3-540-40996-3_22
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41255-7
Online ISBN: 978-3-540-40996-0
eBook Packages: Springer Book Archive