Three-Dimensional Grid Drawings with Sub-quadratic Volume

Dujmovic, Vida and Wood, David R. (2004) Three-Dimensional Grid Drawings with Sub-quadratic Volume. [Conference Paper]

Full text not available from this repository.

Abstract

A three-dimensional grid drawing of a graph is a placement of the vertices at distinct points with integer coordinates, such that the straight line-segments representing the edges are pairwise non-crossing. A O(n^3/2) volume bound is proved for three-dimensional grid drawings of graphs with bounded degree, graphs with bounded genus, and graphs with no bounded complete graph as a minor. The previous best bound for these graph families was O(m^2). These results (partially) solve open problems due to Pach, Thiele, and Tóth [Graph Drawing 1997] and Felsner, Liotta, and Wismath [Graph Drawing 2001].

Item Type:	Conference Paper
Classifications:	G Algorithms and Complexity > G.070 Area / Edge Length P Styles > P.720 Straight-line P Styles > P.060 3D
ID Code:	449
Deposited By:	Selbach, Anna
Deposited On:	08 Dec 2004
Last Modified:	18 Sep 2008 13:08
Alternative Locations:	http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2912&spage=190

Repository Staff Only: item control page

References

Noga Alon, Paul Seymour, and Robin Thomas. A seperator theorem for nonplanar graphs. J. Amer. Math. Soc., 3(4):801-808, 1990.

Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci., 209(1-2):1-45, 1998.

Prosenjit Bose, Jurek Czyzowics, Pat Morin, and David R. Wood. The maximum number of edges in a three-dimensional grid-drawing. In Proc. 19th European Workshop on Computational Geometry, pages 101-103, Germany, 2003. Univ. of Bonn.

Tiziana Calamoneri and Andrea Sterbini. 3D straight-line grid drawing of 4-colorable graphs. Inform. Process. Lett., 63(2):97-102, 1997.

Robert F. Cohen, Peter Eades, Tao Lin, and Frank Ruskey. Three-dimensional graph drawing. Algorithmica, 17(2):199-208, 1996.

Emilio di Giacomo. Drawing series-parallel graphs on restricted integer 3D grids. In these proceedings.

Emilio di Giacomo, Giuseppe Liotta, and Stephen Wismath. Drawing series-parallel graphs on a box. In Proc. 14th Canadian Conf. on Computational Geometry (CCCG '02), pages 149-153. The Univ. of Lethbridge, Canada, 2002.

Emilio di Giacomo and Henk Meijer. Track drawings of graphs with constant queue number. In these proceedings.

Hristo N. Djidjev. A separator theorem. C. R. Acad. Bulgare Sci, 34(5):643-645, 1981.

Vida Dujmovic, Pat Morin, and David R. Wood. Path-width and three-dimensional straight-line grid drawings of graphs. In Michael T. Goodrich and Stephen G. Kobourov, eds., Proc. 10th Int'l Symp. on Graph DRawing (GD '02), volume 2528 of Lecture Notes in Comput. Sci., pages 42-53. Springer, 2002.

Vida Dujmovic and David R. Wood. New results in graph layout. Tech. Report TR-2003-04, School of Computer Science, Carleton Univ., Ottawa, Canada, 2003.

Vida Dujmovic and David R. Wood. Three-partitions of k-trees with applications in graph layout. In Hans L. Bodlaender, ed., Proc. 29th Workshop on Graph Theoretic Concepts in Comput. Sci. (WG '03), Lecture Notes on Comput. Sci. Springer, to appear.

Paul Erdös and László Lovász. Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and Finite Sets, volume 10 of Colloq. Math. Soc. János Bolyai, pages 609-627. North-Holland, 1975.

Stefan Felsner, Giuseppe Liotta, and Stephen Wismath. Straight-line drawings on restricted integer grids in two end three dimensions. In Petra Mutzel, Michael Jünger, and Sebastian Leipert, eds., Proc. 9th Int'l Symp. on Graph Drawing (GD '01), volume 2265 of Lecture Notes in Comput. Sci., pages 328-342. Springer, 2002.

Guillaume Fertin, André Raspaud, and Bruce Reed. On star coloring of graphs. In Andreas Branstädt and Van Bang Le, eds., Proc. 27th Int'l Workshop on Graph-Theoretic Concepts in Computer Science (WG '01), volume 2204 of Lecture Notes in Comput. Sci., pages 140-153. Springer, 2001.

John R. Gilbert, Joan P. Hutchinson, and Robert E. Tarjan. A separator theorem for graphs of bounded genus. J. Algorithms, 5(3):391-407, 1984.

András Gyárfás and Douglas West. Multitrack interval graphs. In Proc. 26th Southeastern Int'l Conf. on Combinatorics, Graph Theory and Computing, volume 109 of Congr. Numer., pages 109-116, 1995.

Toru Hasunuma. Laying out iterated line digraphs using queues. In these proceedings.

Lenwood S. Heath, Frank Thomson Leighton, and Arnold L. Rosenberg. Comparing queues and stacks as mechanisms for laying out graphs. SIAMJ J. Discrete Math., 5(3):398-412, 1992.

Percy J. Heawood. Map colour theorem. Quart. J. Pure Appl. Math., 24:332-338, 1890.

Alexandr V. Kostochka. The minimum Headwiger number for graphs with a given mean degree of vertices. Metody Diskret. Analiz., 38:37-58, 1982.

Michael Molloy and Bruce Reed. Graph colouring and the probabilistic method, volume 23 of Algorithms and Combinatorics. Springer, 2002.

Jaroslav Nesetril and Patrice Ossona de Mendez. Colorings and homomorphisms of miner closed classes. In Boris Aronov, Saugata Basu, Janós Pach, and Micha Sharir, eds., Discrete and Computational Geometry, The Goosman-Pollack Festschrift, volume 25 of Algorithms and Combinatorics. Springer, 2003.

János Pach, Torsten Thiele, and Géza Tóth. Three-dimensional grid drawings of graphs. In Giuseppe Di Battista, ed., Proc. 5th Int'l Symp. on Graph Drawing (GD'97), volume 1353 of Lecture Notes in Comput. Sci., pages 47-51.

Springer, 1997. Also in Bernard Chazelle, Jacob E. Goodman, and Richard Pollack, eds., Advances in discrete and computational geometry, volume 223 of Contempory Mazthematics, pp. 251-255, Amer. Math. Soc., 1999.

Timo Poranen. A new algorithm for drawing series-parallel digraphs in 3D. Tech. Report A-2000-16, Dept. of Computer and Information Sciences, Univ. of Tampere, Finland, 2000.

Andrew Thomason. An extremental function for contractions of graphs. Math. Proc. Cambridge Philos. Soc., 95(2):261-265, 1984.

David R. Wood. Queue layouts, tree-width, and three-dimensional graph drawing. In Manindra Agrawal and Anil Seth, eds., Proc. 22nd Foundations of Software Technology and Theoretical Computer Science (FST TCS '02), volume 2556 of Lecture Notes in Comput. Sci., pages 348-359. Springer, 2002.