# Layouts of graph subdivisions

Vida Dujmović, David R. Wood

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

3 Citations (Scopus)

## 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 sub-divisions. 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 OScript(log n) to OScript(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 OScript(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 OScript(log qn(G)) bends per edge.

Original language English Graph Drawing 12th International Symposium, GD 2004 New York, NY, USA, September 29-October 2, 2004 Revised Selected Papers János Pach Berlin Germany Springer 133-143 11 3540245286 https://doi.org/10.1007/978-3-540-31843-9_15 Published - 1 Dec 2004 Yes Graph Drawing 2004 - New York, United States of AmericaDuration: 29 Sep 2004 → 2 Oct 2004Conference number: 12thhttps://link.springer.com/book/10.1007/b105810 (Proceedings)

### Publication series

Name Lecture Notes in Computer Science Springer 3383 0302-9743

### Conference

Conference Graph Drawing 2004 GD 2004 United States of America New York 29/09/04 → 2/10/04 https://link.springer.com/book/10.1007/b105810 (Proceedings)