Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Stacks, Queues and T ...
Article

Stacks, Queues and Tracks: Layouts of Graph Subdivisions

Vida Dujmović (1), David R. Wood ORCID (2)
(1) School of Computer Science [Ottawa]
(2) Departament de Matemàtica Aplicada II
Download article
Open on HAL
Imported on
March 26, 2015
Published on
January 1, 2005
Last modified on
March 31, 2025
Volume 7
vol. 7
DOI
10.46298/dmtcs.346
License
https://about.hal.science/hal-authorisation-v1
Natural Sciences and Engineering Research Council of Canada
Indicators
1892
Views
2530
Downloads

Stacks, Queues and Tracks: Layouts of Graph Subdivisions

Vida Dujmović (1), David R. Wood ORCID (2)
(1) School of Computer Science [Ottawa]
(2) Departament de Matemàtica Aplicada II
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
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • graph layout
  • graph drawing
  • track layout
  • stack layout
  • queue layout
  • book embedding
  • track-number
  • queue-number
  • stack-number
  • page-number
  • book-thickness
  • 2-track thickness
  • geometric thickness
  • subdivision
  • three-dimensional graph drawing
Cited by

Source: OpenCitations

  • Upward Topological Book Embeddings of DAGs

    SIAM Journal on Discrete Mathematics

    Authors : Emilio Di Giacomo ORCID, Francesco Giordano, Giuseppe Liotta ORCID

    Journal reference : Volume 25, 2011, pp. 479-489

    DOI : 10.1137/080731128

  • Sparsity and Dimension

    arXiv (Cornell University)

    Authors : Gwenaël Joret, Piotr Micek, Veit Wiechert

    Journal reference : Volume 38, 2017, pp. 1129-1148

    DOI : 10.1007/s00493-017-3638-4

  • (3,2)-Track Layout of Bipartite Graph Subdivisions

    Lecture notes in computer science

    Authors : Miki Miyauchi

    Journal reference : Volume , 2008, pp. 127-131

    DOI : 10.1007/978-3-540-89550-3_14

  • Mixed Linear Layouts of Planar Graphs

    arXiv (Cornell University)

    Authors : Sergey Pupyrev ORCID

    Journal reference : Volume , 2018, pp. 197-209

    DOI : 10.1007/978-3-319-73915-1_17

  • Upward Three-Dimensional Grid Drawings of Graphs

    arXiv (Cornell University)

    Authors : Vida Dujmović ORCID, David R. Wood ORCID

    Journal reference : Volume 23, 2006, pp. 1-20

    DOI : 10.1007/s11083-006-9028-y

  • Track Layout Is Hard

    Lecture notes in computer science

    Authors : Michael J. Bannister, William E. Devanny, Vida Dujmović ORCID, David Eppstein, David R. Wood ORCID

    Journal reference : Volume , 2016, pp. 499-510

    DOI : 10.1007/978-3-319-50106-2_38

  • Layered separators in minor-closed graph classes with applications

    Journal of Combinatorial Theory Series B

    Authors : Vida Dujmović ORCID, Pat Morin ORCID, David R. Wood ORCID

    Journal reference : Volume 127, 2017, pp. 111-147

    DOI : 10.1016/j.jctb.2017.05.006

  • On the Queue Number of Planar Graphs

    Infoscience (Ecole Polytechnique Fédérale de Lausanne)

    Authors : Giuseppe Di Battista ORCID, Fabrizio Frati ORCID, János Pach ORCID

    Journal reference : Volume 42, 2013, pp. 2243-2285

    DOI : 10.1137/130908051

  • Three-Dimensional Graph Drawing

    Encyclopedia of Algorithms

    Authors : David R. Wood ORCID

    Journal reference : Volume , 2014, pp. 1-7

    DOI : 10.1007/978-3-642-27848-8_656-1

  • On the Pagenumber of the Cube-Connected Cycles

    Mathematics in Computer Science

    Authors : Yuuki Tanaka ORCID, Yukio Shibata

    Journal reference : Volume 3, 2009, pp. 109-117

    DOI : 10.1007/s11786-009-0012-y

  • Animation of an Algorithm for Drawing Graphs in 3D

    Proceedings of the thirtieth annual symposium on Computational geometry

    Authors : Lezar DeGuzman, Stephen Wismath ORCID

    Journal reference : Volume , 2014, pp. 92-93

    DOI : 10.1145/2582112.2595648

  • Three-Dimensional Graph Products with Unbounded Stack-Number

    Discrete & Computational Geometry

    Authors : David Eppstein, Robert Hickingbotham ORCID, Laura Merker ORCID, Sergey Norin ORCID, Michał T. Seweryn ORCID, David R. Wood ORCID

    Journal reference : Volume 71, 2023, pp. 1210-1237

    DOI : 10.1007/s00454-022-00478-6

  • Shallow Minors, Graph Products, and Beyond-Planar Graphs

    SIAM Journal on Discrete Mathematics

    Authors : Robert Hickingbotham ORCID, David R. Wood ORCID

    Journal reference : Volume 38, 2024, pp. 1057-1089

    DOI : 10.1137/22m1540296

  • Stack and Queue Numbers of Graphs Revisited

    Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications

    Authors : Petr Hlineny ORCID, Adam Straka

    Journal reference : Volume , 2023, pp. 601-606

    DOI : 10.5817/cz.muni.eurocomb23-083

  • Planar Graphs of Bounded Degree Have Bounded Queue Number

    SIAM Journal on Computing

    Authors : Michael A. Bekos ORCID, Henry Förster ORCID, Martin Gronemann ORCID, Tamara Mchedlidze ORCID, Fabrizio Montecchiani ORCID, Chrysanthi Raftopoulou ORCID, Torsten Ueckerdt ORCID

    Journal reference : Volume 48, 2019, pp. 1487-1502

    DOI : 10.1137/19m125340x

  • Stack-Number is Not Bounded by Queue-Number

    arXiv (Cornell University)

    Authors : Vida Dujmović ORCID, David Eppstein, Robert Hickingbotham ORCID, Pat Morin ORCID, David R. Wood ORCID

    Journal reference : Volume 42, 2021, pp. 151-164

    DOI : 10.1007/s00493-021-4585-7

  • Drawing K n in Three Dimensions with One Bend Per Edge

    Lecture notes in computer science

    Authors : Olivier Devillers ORCID, Hazel Everett, Sylvain Lazard ORCID, Maria Pentcheva, Stephen K. Wismath ORCID

    Journal reference : Volume , 2006, pp. 83-88

    DOI : 10.1007/11618058_8

  • Volume requirements of 3D upward drawings

    Discrete Mathematics

    Authors : Emilio Di Giacomo ORCID, Giuseppe Liotta ORCID, Henk Meijer ORCID, Stephen K. Wismath ORCID

    Journal reference : Volume 309, 2008, pp. 1824-1837

    DOI : 10.1016/j.disc.2007.12.061

  • On the Stack Number and the Queue Number of the Bubble-Sort Graph

    IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences

    Authors : Yuuki TANAKA ORCID

    Journal reference : Volume E99.A, 2016, pp. 1012-1018

    DOI : 10.1587/transfun.e99.a.1012

  • Plane Drawings of Queue and Deque Graphs

    Lecture notes in computer science

    Authors : Christopher Auer, Christian Bachmaier, Franz Josef Brandenburg ORCID, Wolfgang Brunner, Andreas Gleißner ORCID

    Journal reference : Volume , 2011, pp. 68-79

    DOI : 10.1007/978-3-642-18469-7_7

  • Queue Layouts of Hypercubes

    SIAM Journal on Discrete Mathematics

    Authors : Petr Gregor ORCID, Riste Škrekovski ORCID, Vida Vukašinović ORCID

    Journal reference : Volume 26, 2012, pp. 77-88

    DOI : 10.1137/100813865

  • Characterisations and examples of graph classes with bounded expansion

    European Journal of Combinatorics

    Authors : Jaroslav Nešetřil ORCID, Patrice Ossona de Mendez ORCID, David R. Wood ORCID

    Journal reference : Volume 33, 2011, pp. 350-373

    DOI : 10.1016/j.ejc.2011.09.008

  • Topological Graph Layouts into a Triangular Prism

    Lecture notes in computer science

    Authors : Miki Miyauchi

    Journal reference : Volume , 2016, pp. 241-246

    DOI : 10.1007/978-3-319-48532-4_21

  • Stack and queue numbers of graphs revisited

    European Journal of Combinatorics

    Authors : Petr Hliněný ORCID, Adam Straka

    Journal reference : Volume 129, 2024, pp. 104094

    DOI : 10.1016/j.ejc.2024.104094

  • Graph layouts via layered separators

    Journal of Combinatorial Theory Series B

    Authors : Vida Dujmović ORCID

    Journal reference : Volume 110, 2014, pp. 79-89

    DOI : 10.1016/j.jctb.2014.07.005

  • Three-Dimensional Graph Drawing

    Encyclopedia of Algorithms

    Authors : David R. Wood ORCID

    Journal reference : Volume , 2016, pp. 2231-2236

    DOI : 10.1007/978-1-4939-2864-4_656

  • Topological Stack-Queue Mixed Layouts of Graphs

    IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences

    Authors : Miki MIYAUCHI

    Journal reference : Volume E103.A, 2020, pp. 510-522

    DOI : 10.1587/transfun.2019eap1097
Preview
Loading PDF preview...