Layouts of Graph Subdivisions

Dujmovic, Vida and Wood, David R. (2004) Layouts of Graph Subdivisions. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 133-143 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_15).

Full text not available from this repository.

Abstract

A k-stack layout (respectively, k-queue layout) of a graph consists of a total order of the vertices, and a partition of the edges into k sets of non-crossing (non-nested) edges with respect to the vertex ordering. A k-track layout of a graph consists of a vertex k-colouring, and a total order of each vertex colour class, such that between each pair of colour classes no two edges cross. The stack-number (respectively, queue-number, track-number) of a graph G, denoted by sn (G) (qn(G), tn(G) is the minimum k such that G has a k-stack (k-queue, k-track) layout. This paper studies stack, queue, and track layouts of graph subdivisions. It is known that every graph has a 3-stack subdivision. The best known upper bound on the number of division vertices per edge in a 3-stack subdivision of an n-vertex graph G is improved from O(log n) to O(log min{sn(G), qn(G)}). This result reduces the question of whether queue-number is bounded by stack-number to whether 3-stack graphs have bounded queue number. It is proved that every graph has a 2-queue subdivision, a 4-track subdivision, and a mixed 1-stack 1-queue subdivision. All these values are optimal for every non-planar graph. In addition, we characterise those graphs with k-stack, k-queue, and k-track subdivisions, for all values of k. The number of division vertices per edge in the case of 2-queue and 4-track subdivisions, namely 0(log qn(G)), is optimal to within a constant factor, for every graph G. Applications to 3D polyline grid drawings are presented. For example, it is proved that every graph G has a 3D polyline grid drawing with the vertices on a rectangular prism, and with O(log qn(G)) bends per edge. Research supported by NSERC and COMBSTRU.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_15
Classifications:G Algorithms and Complexity > G.420 Crossings
Z Theory > Z.500 Representations
ID Code:580

Repository Staff Only: item control page

References

Robin Blankenship and Bogdan Oporowski. Drawing subdivisions of complete and complete bipartite graphs on books. Technical Report 1999-4, Department of Mathematics, Louisiana State University, 1999.

Prosenjit Bose, Jurek Czyzowicz, Pat Morin, and Davis R. Wood. The maximum number of edges in a three-dimensional grid-drawing. J. Graph Algorithms Appl., 8(1):21-26, 2004.

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

Emilio Di Giacomo and Henk Meijer. Track drawings of graphs with constant queue number. In Liotta [16], pages 214-225.

Vida Dujmovic, Pat Morin, and David R. Wood. Layout of graphs with bounded tree-width. SIAM J. Comput., to appear.

Vida Dujmovic,Attila Pór, and David R. Wood. Track layouts of graphs. Submitted; see arXiv:cs.DM/0407033, 2004.

Vida Dujmovic and David R. Wood. Stacks, queues and tracks: Layouts of graph subdivisions. Submitted; see Tech. Rep. TR-2003-08, School of Computer Science, Carleton University, Ottawa, Canada, 2003.

Vida Dujmovic and David R. Wood. On linear layouts of graphs. Discrete Math. Theor. Comput. Sci., 6(2):339-358, 2004.

Vida Dujmovic and David R. Wood. Three-dimensional grid drawings with sub-quadratic volume. In Pach [18], pages 55-66.

Hikoe Enomoto and Miki Shimabara Miyauchi. Embedding graphs into a three page book with 0(M log N) crossings of edges over the spine. SIAM J. Discrete Math., 12(3):337-341, 1999.

Hikoe Enomoto and Miki Shimabara Miyauchi. Embedding a graph into a d + 1-page book with [m log_d^n] edge-crossings over the spine. IPSJ SIGNotes ALgorithms, 051, 2001. Abstract No. 008.

Hikoe Enomoto, Miki Shimabara Miyauchi, and Katsuhiro Ota. Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph. Discrete Appl. Math., 92(2-3):149-155, 1999.

David Eppstein. Separating thickness from geometric thickness. In Pach [18], pages 75-86.

Stefan Felsner, Giuseppe Liotta, and Stephen Wismath. Straight-line drawings on restricted integer grids in two and three dimensions. J. Graph Algorithms Appl., 7(4):363-398, 2003.

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

Guiseppe Liotta, editor. Proc. 11th International Symp. on Graph Drawing (GD'03), volume 2912 of Lecture Notes in Computer Sci. Springer, 2004.

Miki Shimabara Miyauchi. An 0(nm) algorithm for embedding graphs into a 3-page book. Trans. IEICE, E77-A(3):521-526, 1994.

János Pach, editor. Towards a Theory of Geometric Graphs, volume 342 of Contemporary Mathematics. Amer. Math. Soc., 2004.

János Pach, Torsten Thiele, and Géza Toth. Three-dimensional grid drawings of graphs. In Bernard Chazelle, Jacob E. Goodman, and Richard Pollack, editors, Advances in discrete and computational geometry, volume 223 of Contemporary Mathematics, pages 251-255. Amer. Math. Soc., 1999.