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. On Linear Layouts of ...
Article

On Linear Layouts of Graphs

Vida Dujmović (1), David R. Wood ORCID (1) (2)
(1) School of Computer Science [Ottawa]
(2) 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.317
License
https://about.hal.science/hal-authorisation-v1
Natural Sciences and Engineering Research Council of Canada
Indicators
1384
Views
2003
Downloads

On Linear Layouts of Graphs

Vida Dujmović (1), David R. Wood ORCID (1) (2)
(1) School of Computer Science [Ottawa]
(2) Department of Applied Mathematics [Prague]
Abstract
In a total order of the vertices of a graph, two edges with no endpoint in common can be \emphcrossing, \emphnested, or \emphdisjoint. A \emphk-stack (respectively, \emphk-queue, \emphk-arch) \emphlayout of a graph consists of a total order of the vertices, and a partition of the edges into k sets of pairwise non-crossing (non-nested, non-disjoint) edges. Motivated by numerous applications, stack layouts (also called \emphbook embeddings) and queue layouts are widely studied in the literature, while this is the first paper to investigate arch layouts.\par Our main result is a characterisation of k-arch graphs as the \emphalmost (k+1)-colourable graphs; that is, the graphs G with a set S of at most k vertices, such that G S is (k+1)-colourable.\par In addition, we survey the following fundamental questions regarding each type of layout, and in the case of queue layouts, provide simple proofs of a number of existing results. How does one partition the edges given a fixed ordering of the vertices? What is the maximum number of edges in each type of layout? What is the maximum chromatic number of a graph admitting each type of layout? What is the computational complexity of recognising the graphs that admit each type of layout?\par A comprehensive bibliography of all known references on these topics is included. \par
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • graph layout
  • graph drawing
  • stack layout
  • queue layout
  • arch layout
  • book embedding
  • queue-number
  • stack-number
  • page-number
  • book-thickness
Cited by

Source: OpenCitations

  • Defective Colouring of Graphs Excluding A Subgraph or Minor

    arXiv (Cornell University)

    Authors : Patrice Ossona De Mendez ORCID, Sang-Il Oum ORCID, David R. Wood ORCID

    Journal reference : Volume 39, 2018, pp. 377-410

    DOI : 10.1007/s00493-018-3733-1

  • Queue Layouts of Toroidal Grids

    IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences

    Authors : Kung-Jui PAI ORCID, Jou-Ming CHANG ORCID, Yue-Li WANG, Ro-Yu WU

    Journal reference : Volume E97.A, 2014, pp. 1180-1186

    DOI : 10.1587/transfun.e97.a.1180

  • Directed Acyclic Outerplanar Graphs Have Constant Stack Number

    TheoretiCS

    Authors : Paul Jungeblut ORCID, Laura Merker ORCID, Torsten Ueckerdt ORCID

    Journal reference : Volume Volume 4, 2025, pp.

    DOI : 10.46298/theoretics.25.25

  • QUBO Formulation for the Minimum Linear Arrangement Problem

    2025 29th International Computer Science and Engineering Conference (ICSEC)

    Authors : Pawaret Dilokwuttisit

    Journal reference : Volume , 2025, pp. 173-181

    DOI : 10.1109/icsec67360.2025.11298119

  • The Peculiarities of Extending Queue Layouts

    Lecture notes in computer science

    Authors : Thomas Depian ORCID, Simon D. Fink ORCID, Robert Ganian ORCID, Martin Nöllenburg ORCID

    Journal reference : Volume , 2026, pp. 177-191

    DOI : 10.1007/978-3-032-11835-6_13

  • Directed Acyclic Outerplanar Graphs Have Constant Stack Number

    2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)

    Authors : Paul Jungeblut ORCID, Laura Merker ORCID, Torsten Ueckerdt ORCID

    Journal reference : Volume 9, 2023, pp. 1937-1952

    DOI : 10.1109/focs57990.2023.00118

  • Defective and Clustered Graph Colouring

    The Electronic Journal of Combinatorics

    Authors : David R. Wood ORCID

    Journal reference : Volume 1000, 2018, pp.

    DOI : 10.37236/7406

  • Parameterized Algorithms for Book Embedding Problems

    Journal of Graph Algorithms and Applications

    Authors : Sujoy Bhore ORCID, Robert Ganian ORCID, Fabrizio Montecchiani ORCID, Martin Nöllenburg ORCID

    Journal reference : Volume 24, 2019, pp. 365-378

    DOI : 10.1007/978-3-030-35802-0_28

  • A Survey on Graph Drawing Beyond Planarity

    arXiv (Cornell University)

    Authors : Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani

    Journal reference : Volume 52, 2019, pp. 1-37

    DOI : 10.1145/3301281

  • 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

  • Local and Union Page Numbers

    arXiv (Cornell University)

    Authors : Laura Merker ORCID, Torsten Ueckerdt ORCID

    Journal reference : Volume , 2019, pp. 447-459

    DOI : 10.1007/978-3-030-35802-0_34

  • Upward Book Embeddings of st-Graphs

    DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

    Authors : Carla Binucci ORCID, Giordano Da Lozzo ORCID, Emilio Di Giacomo ORCID, Walter Didimo ORCID, Tamara Mchedlidze ORCID, Maurizio Patrignani ORCID

    Journal reference : Volume 129, 2019, pp. 22

    DOI : 10.4230/lipics.socg.2019.13

  • Graph Drawings with One Bend and Few Slopes

    arXiv (Cornell University)

    Authors : Kolja Knauer ORCID, Bartosz Walczak ORCID

    Journal reference : Volume , 2016, pp. 549-561

    DOI : 10.1007/978-3-662-49529-2_41

  • Oriented Spanners

    Algorithmica

    Authors : Kevin Buchin ORCID, Joachim Gudmundsson ORCID, Antonia Kalb, Aleksandr Popov ORCID, Carolin Rehs ORCID, André van Renssen ORCID, Sampson Wong ORCID

    Journal reference : Volume 88, 2025, pp.

    DOI : 10.1007/s00453-025-01342-8

  • Two-Page Book Embeddings of 4-Planar Graphs

    Algorithmica

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

    Journal reference : Volume 75, 2015, pp. 158-185

    DOI : 10.1007/s00453-015-0016-8

  • On Mixed Linear Layouts of Series-Parallel Graphs

    Lecture notes in computer science

    Authors : Patrizio Angelini ORCID, Michael A. Bekos ORCID, Philipp Kindermann ORCID, Tamara Mchedlidze ORCID

    Journal reference : Volume , 2020, pp. 151-159

    DOI : 10.1007/978-3-030-68766-3_12

  • Chromatic Number of Ordered Graphs with Forbidden Ordered Subgraphs

    arXiv (Cornell University)

    Authors : Maria Axenovich ORCID, Jonathan Rollin ORCID, Torsten Ueckerdt ORCID

    Journal reference : Volume 38, 2017, pp. 1021-1043

    DOI : 10.1007/s00493-017-3593-0

  • Parameterized Algorithms for Queue Layouts

    Journal of Graph Algorithms and Applications

    Authors : Sujoy Bhore ORCID, Robert Ganian ORCID, Fabrizio Montecchiani ORCID, Martin Nöllenburg ORCID

    Journal reference : Volume 26, 2022, pp. 335-352

    DOI : 10.7155/jgaa.00597

  • On the Book Thickness of k-Trees

    Discrete Mathematics & Theoretical Computer Science

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

    Journal reference : Volume Vol. 13 no. 3, 2011, pp.

    DOI : 10.46298/dmtcs.550

  • 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...