Abstract
This paper investigates the following question: Given an integer grid ϕ, where ϕ is a proper subset of the integer plane or a proper subset of the integer 3d space, which graphs admit straight-line crossingfree drawings with vertices located at the grid points of ϕ? We characterize the trees that can be drawn on a two dimensional c · n × к grid, where к and c are given integer constants, and on a two dimensional grid consisting of к parallel horizontal lines of infinite length. Motivated by the results on the plane we investigate restrictions of the integer grid in 3 dimensions and show that every outerplanar graph with n vertices can be drawn crossing-free with straight lines in linear volume on a grid called a prism. This prism consists of 3n integer grid points and is universal — it supports all outerplanar graphs of n vertices. This is the first algorithm that computes crossing-free straight line 3d drawings in linear volume for a non-trivial family of planar graphs. We also show that there exist planar graphs that cannot be drawn on the prism and that the extension to a n × 2 × 2 integer grid, called a box, does not admit the entire class of planar graphs.
Research supported in part by the CNR Project “Geometria Computazionale Robusta con Applicazioni alla Grafica ed al CAD”, the project “Algorithms for Large Data Sets: Science and Engineering” of the Italian Ministry of University and Scientific and Technological Research (MURST 40%); and by the Natural Sciences and Engineering Council of Canada.
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
T. Calamoneri and A. Sterbini. Drawing 2-, 3-, and 4-colorable graphs in o(n 2) volume. In S. North, editor, Graph Drawing (Proc. GD’ 96), volume 1190 of Lecture Notes Comput. Sci., pages 53–62. Springer-Verlag, 1997.
T.M. Chan. A near-linear area bound for drawing binary trees. In Proc. 10th Annu. ACM-SIAM Sympos. on Discrete Algorithms., pages 161–168, 1999.
M. Chrobak and G. Kant. Convex grid drawings of 3-connected planar graphs. Internat. J. Comput. Geom. Appl., 7(3):211–223, 1997.
Marek Chrobak, Michael T. Goodrich, and Roberto Tamassia. Convex drawings of graphs in two and three dimensions. In Proc. 12th Annu. ACM Sympos. Comput. Geom., pages 319–328, 1996.
Marek Chrobak and Shin ichi Nakano. Minimum-width grid drawings of plane graphs. Comput. Geom. Theory Appl., 11:29–54, 1998.
R. F. Cohen, P. Eades, T. Lin, and F. Ruskey. Three-dimensional graph drawing. Algorithmica, 17:199–208, 1997.
H. de Fraysseix, J. Pach, and R. Pollack. Small sets supporting Fary embeddings of planar graphs. In Proc. 20th ACMSymp os. Theory Comput., pages 426–433, 1988.
H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10(1):41–51, 1990.
G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.
Reinhard Diestel. Graph theory. Graduate Texts in Mathematics. 173. Springer, 2000. Transl. from the German. 2nd ed.
V. Dujmovic, M. Fellows, M. Hallett, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, M. Suderman, S. Whitesides, D. R. Wood. On the Parameterized Complexity of Layered Graph Drawing. ESA, 1–12, 2001.
Stefan Felsner. Convex drawings of planar graphs and the order dimension of 3-polytopes. Order-accepted to appear.
A. Garg, M. T. Goodrich, and R. Tamassia. Planar upward tree drawings with optimal area. Internat. J. Comput. Geom. Appl., 6:333–356, 1996.
A. Garg, R. Tamassia, and P. Vocca. Drawing with colors. In Proc. 4th Annu. European Sympos. Algorithms, volume 1136 of Lecture Notes Comput. Sci., pages 12–26. Springer-Verlag, 1996.
Michael Juenger and Sebastian Leipert. Level planar embedding in linear time. In J. Kratochvil, editor, Graph Drawing (Proc. GD’ 99), volume 1731 of Lecture Notes Comput. Sci., pages 72–81. Springer-Verlag, 1999.
G. Kant. A new method for planar graph drawings on a grid. In Proc. 33rd Annu. IEEE Sympos. Found. Comput. Sci., pages 101–110, 1992.
G. Kant. Drawing planar graphs using the canonical ordering. Algorithmica, 16:4–32, 1996.
János Pach, Torsten Thiele, and Géza Tóth. Three-dimensional grid drawings of graphs. In G. Di Battista, editor, Graph Drawing (Proc. GD’ 97), volume 1353 of Lecture Notes Comput. Sci., pages 47–51. Springer-Verlag, 1997.
F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, 3rd edition, October 1990.
W. Schnyder. Embedding planar graphs on the grid. In Proc. 1st ACM-SIAM Sympos. Discrete Algorithms, pages 138–148, 1990.
W. Schnyder and W. T. Trotter. Convex embeddings of 3-connected plane graphs. Abstracts of the AMS, 13(5):502, 1992.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Felsner, S., Liotta, G., Wismath, S. (2002). Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions. In: Mutzel, P., Jünger, M., Leipert, S. (eds) Graph Drawing. GD 2001. Lecture Notes in Computer Science, vol 2265. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45848-4_26
Download citation
DOI: https://doi.org/10.1007/3-540-45848-4_26
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43309-5
Online ISBN: 978-3-540-45848-7
eBook Packages: Springer Book Archive