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. Track Layouts of Gra ...
Article

Track Layouts of Graphs

Vida Dujmović (1), Attila Pór (2), David R. Wood ORCID (1) (3)
(1) School of Computer Science [Ottawa]
(2) Department of Mathematics, Applied Mathematics and Statistics [Cleveland]
(3) Department of Applied Mathematics [Prague]
Download article
Open on HAL
Imported on
March 26, 2015
Published on
January 1, 2004
Last modified on
March 31, 2025
Volume 6
vol. 6:2
DOI
10.46298/dmtcs.315
License
https://about.hal.science/hal-authorisation-v1
Natural Sciences and Engineering Research Council of Canada
Indicators
1682
Views
1719
Downloads

Track Layouts of Graphs

Vida Dujmović (1), Attila Pór (2), David R. Wood ORCID (1) (3)
(1) School of Computer Science [Ottawa]
(2) Department of Mathematics, Applied Mathematics and Statistics [Cleveland]
(3) Department of Applied Mathematics [Prague]
Abstract
A \emph(k,t)-track layout of a graph G consists of a (proper) vertex t-colouring of G, a total order of each vertex colour class, and a (non-proper) edge k-colouring such that between each pair of colour classes no two monochromatic edges cross. This structure has recently arisen in the study of three-dimensional graph drawings. This paper presents the beginnings of a theory of track layouts. First we determine the maximum number of edges in a (k,t)-track layout, and show how to colour the edges given fixed linear orderings of the vertex colour classes. We then describe methods for the manipulation of track layouts. For example, we show how to decrease the number of edge colours in a track layout at the expense of increasing the number of tracks, and vice versa. We then study the relationship between track layouts and other models of graph layout, namely stack and queue layouts, and geometric thickness. One of our principle results is that the queue-number and track-number of a graph are tied, in the sense that one is bounded by a function of the other. As corollaries we prove that acyclic chromatic number is bounded by both queue-number and stack-number. Finally we consider track layouts of planar graphs. While it is an open problem whether planar graphs have bounded track-number, we prove bounds on the track-number of outerplanar graphs, and give the best known lower bound on the track-number of planar graphs.\
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
  • geometric thickness
  • three-dimensional graph drawing
Cited by

Source: OpenCitations

  • The Complexity of Drawing Graphs on Few Lines and Few Planes

    Journal of Graph Algorithms and Applications

    Authors : Steven Chaplick ORCID, Krzysztof Fleszar ORCID, Fabian Lipp ORCID, Alexander Ravsky, Oleg Verbitsky ORCID, Alexander Wolff ORCID

    Journal reference : Volume 27, 2023, pp. 459-488

    DOI : 10.7155/jgaa.00630

  • A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs

    Society for Industrial and Applied Mathematics eBooks

    Authors : Ajaykrishnan E S, Robert Ganian ORCID, Daniel Lokshtanov ORCID, Vaishali Surianarayanan ORCID

    Journal reference : Volume , 2026, pp. 65-80

    DOI : 10.1137/1.9781611978964.6

  • 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

  • Layouts of Graph Subdivisions

    Lecture notes in computer science

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

    Journal reference : Volume , 2005, pp. 133-143

    DOI : 10.1007/978-3-540-31843-9_15

  • Queue Layouts of Two-Dimensional Posets

    Lecture notes in computer science

    Authors : Sergey Pupyrev ORCID

    Journal reference : Volume , 2023, pp. 353-360

    DOI : 10.1007/978-3-031-22203-0_25

  • 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

  • On the Queue Number of Planar Graphs

    arXiv (Cornell University)

    Authors : Michael A. Bekos ORCID, Martin Gronemann ORCID, Chrysanthi N. Raftopoulou ORCID

    Journal reference : Volume , 2021, pp. 271-284

    DOI : 10.1007/978-3-030-92931-2_20

  • Geometric Thickness of Multigraphs is $$\exists \mathbb {R}$$-Complete

    Algorithmica

    Authors : Henry Förster ORCID, Philipp Kindermann ORCID, Tillmann Miltzow ORCID, Irene Parada ORCID, Soeren Terziadis ORCID, Birgit Vogtenhuber ORCID

    Journal reference : Volume 88, 2025, pp.

    DOI : 10.1007/s00453-025-01351-7

  • On 3-Coloring Circle Graphs

    Lecture notes in computer science

    Authors : Patricia Bachmann ORCID, Ignaz Rutter ORCID, Peter Stumpf ORCID

    Journal reference : Volume , 2023, pp. 152-160

    DOI : 10.1007/978-3-031-49272-3_11

  • 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

  • The Complexity of Drawing Graphs on Few Lines and Few Planes

    Lecture notes in computer science

    Authors : Steven Chaplick ORCID, Krzysztof Fleszar ORCID, Fabian Lipp ORCID, Alexander Ravsky, Oleg Verbitsky ORCID, Alexander Wolff ORCID

    Journal reference : Volume , 2017, pp. 265-276

    DOI : 10.1007/978-3-319-62127-2_23

  • Lifting Maps Between Graphs to Embeddings

    Essays on Topology

    Authors : Alexey Gorelov

    Journal reference : Volume , 2025, pp. 327-364

    DOI : 10.1007/978-3-031-81414-3_16

  • Weakly leveled planarity with bounded span

    Theoretical Computer Science

    Authors : Michael A. Bekos, Giordano Da Lozzo ORCID, Fabrizio Frati ORCID, Siddharth Gupta, Philipp Kindermann ORCID, Giuseppe Liotta, Ignaz Rutter, Ioannis G. Tollis ORCID

    Journal reference : Volume 1069, 2026, pp. 115811

    DOI : 10.1016/j.tcs.2026.115811
Preview
Loading PDF preview...