Vida Dujmović ; David R. Wood - Stacks, Queues and Tracks: Layouts of Graph Subdivisions

dmtcs:346 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, Vol. 7 -
Stacks, Queues and Tracks: Layouts of Graph Subdivisions

Authors: Vida Dujmović 1; David R. Wood ORCID-iD2

  • 1 School of Computer Science [Ottawa]
  • 2 Departament de Matemàtica Aplicada II

A \emphk-stack layout (respectively, \emphk-queuelayout) 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 \emphk-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 \emphstack-number (respectively, \emphqueue-number, \emphtrack-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.\par 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.\par 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. \par 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. \par

Volume: Vol. 7
Published on: January 1, 2005
Imported on: March 26, 2015
Keywords: 2-track thickness,book-thickness,page-number,graph layout,graph drawing,track layout,stack layout,queue layout,book embedding,track-number,queue-number,stack-number,three-dimensional graph drawing,geometric thickness,subdivision,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 0902.3265
Source : ScholeXplorer IsRelatedTo DOI 10.1016/j.ejc.2011.09.008
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.0902.3265
  • 10.1016/j.ejc.2011.09.008
  • 10.48550/arxiv.0902.3265
  • 0902.3265
Characterisations and examples of graph classes with bounded expansion

19 Documents citing this article

Consultation statistics

This page has been seen 539 times.
This article's PDF has been downloaded 396 times.