×

Stacks, queues and tracks: layouts of graph subdivisions. (English) Zbl 1153.05036

Summary: 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 \(O(\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. Finally, we establish a tight relationship between queue layouts and so-called \(2\)-track thickness of bipartite graphs.

MSC:

05C62 Graph representations (geometric and intersection representations, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: EuDML Link