Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions (Extended Abstract)

Felsner, Stefan and Liotta, Giuseppe and Wismath, Stephen (2002) Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions (Extended Abstract). In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001, Vienna, Austria , pp. 328-342 (Official URL: http://dx.doi.org/10.1007/3-540-45848-4_26).

Full text not available from this repository.

Abstract

This paper investigates the following question: Given an integer grid $\phi$, where $\phi$ is a proper subset of the integer plane or a proper subset of the integer 3d space, which graphs admit straight-line crossing-free drawings with vertices located at the grid points of $\phi$? We characterize the trees that can be drawn on a two dimensional $c \cdot n \times k$ grid, where $k$ and $c$ are given integer constants, and on a two dimensional grid consisting of $k$ 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 \times 2 \times 2$ integer grid, called a box, does not admit the entire class of planar graphs.

Item Type:Conference Paper
Additional Information:10.1007/3-540-45848-4_26
Classifications:P Styles > P.720 Straight-line
M Methods > M.600 Planar
G Algorithms and Complexity > G.420 Crossings
P Styles > P.060 3D
ID Code:518

Repository Staff Only: item control page

References

T. Calamoneri and A. Sterbini. Drawing 2-,3-, and 4-colorable graphs in O(n²) volume. In S. North, editor: Proceedings of Graph Drawing '96 (Proc. GD '96), vol. 1190 of LNCS, pp. 53-62, Springer-Verlag, 1997.

T.M. Chan. A near-linear area bound for drawing binary trees. In Proc. 10th Annu. ACM-SIAM Symp. on Discrete Algorithms, pages 161-168, 1999.

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

M. Chrobak, M.T. Goodrich, and R. Tamassia. Convex drawings of graphs in two and three dimensions. In Proc. 12th Annu. ACM Sympos. Comput. Geom., pages 319-328, 1996.

M. Chrobak and S. 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(2):199-208, 1996.

H. de Fraysseix, J. Pach, and R. Pollack. Small sets supporting Fary embeddings of planar graphs. In Proc. 20th Annu. ACM Sympos. 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:41-51, 1990.

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.

R. Diestel. Graph Theory. Graduate Texts in Mathematics. 173. Springer, 2000. Transl. from ger. 2nd edition.

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.

S. 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. International Journal of Computational Geometry and Applications, 6(3):333-356, 1996.

A. Garg, R. Tamassia, and P. Vocca. Drawing with colors. In Pco. 4th Annu. European Symp. Algorithms (ESA '96), vol. 1136 of LNCS, pp. 12-26, Springer-Verlag, 1996.

M. Jünger and S. Leipert. Level planar embedding in linear time. In J. Kratochvíl, editor, Proc. Graph Drawing: 7th International Symp. (GD '99), Lecture Notes in Comput. Sci., pages 72-81, Berlin. Springer.

G. Kant. A new method for planar graph drawins on a grid. In Proc. 33rd Annu. IEEE Sympos. Found. Comput. Sci., pages 101-110, 1992.

Goos Kant. Drawing planar graphs using the canonical ordering. Algorithmica, 16:4-32, 1996.

J. Pach, T. Thiele, and G. Tóth. Three-dimensional grid drawings of graphs. In G. Di Battista, editor: Proceedings of Graph Drawing '97 (Proc. GD '97), vol. 1353 of LNCS, pp. 47-51. Springer-Verlag, 1998.

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 Symp. Discrete Algorithms, pages 138-148, 1990.

W. Schnyder and W.T. Trotter. Convex embeddings of three-connected plane graphs. Abstracts of the AMS, 13(5):502, 1992.