Stacks, Queues and Tracks: Layouts of Graph Subdivisions

Abstract : 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
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2005, 7, pp.155-202
Liste complète des métadonnées

https://hal.inria.fr/hal-00959036
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 13 mars 2014 - 17:08:17
Dernière modification le : mardi 6 février 2018 - 14:48:02
Document(s) archivé(s) le : vendredi 13 juin 2014 - 12:17:15

Fichier

dm070111.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00959036, version 1

Collections

Citation

Vida Dujmović, David R. Wood. Stacks, Queues and Tracks: Layouts of Graph Subdivisions. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2005, 7, pp.155-202. 〈hal-00959036〉

Partager

Métriques

Consultations de la notice

119

Téléchargements de fichiers

110