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 - https://doi.org/10.46298/dmtcs.346
Stacks, Queues and Tracks: Layouts of Graph Subdivisions

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

    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]
    Fundings :
      Source : OpenAIRE Research Graph
    • Funder: Natural Sciences and Engineering Research Council of Canada

    16 Documents citing this article

    Share

    Consultation statistics

    This page has been seen 445 times.
    This article's PDF has been downloaded 322 times.