Planar graphs of bounded degree have bounded queue number

DOI10.1137/19M125340XMaRDI QIDQ5235482zbMATH OpenOpenAlexWikidataFDO

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

Publication date 11 October 2019

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.00816

zbMATH Keywords

planar graphsqueue number

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: A emph{queue layout} of a graph consists of a emph{linear order} of its vertices and a partition of its edges into emph{queues}, so that no two independent edges of the same queue are nested. The emph{queue number} of a graph is the minimum number of queues required by any of its queue layouts. A long-standing conjecture by Heath, Leighton and Rosenberg states that the queue number of planar graphs is bounded. This conjecture has been partially settled in the positive for several subfamilies of planar graphs (most of which have bounded treewidth). In this paper, we make a further important step towards settling this conjecture. We prove that planar graphs of bounded degree (which may have unbounded treewidth) have bounded queue number. A notable implication of this result is that every planar graph of bounded degree admits a three-dimensional straight-line grid drawing in linear volume. Further implications are that every planar graph of bounded degree has bounded track number, and that every $k$-planar graph (i.e., every graph that can be drawn in the plane with at most $k$ crossings per edge) of bounded degree has bounded queue number.

Recommendations

• Planar graphs of bounded degree have bounded queue number
• On the Queue Number of Planar Graphs
• scientific article; zbMATH DE number 1954397
• Layout of Graphs with Bounded Tree-Width
• Graph layouts via layered separators

Cites work

• scientific article; zbMATH DE number 1974106 (Why is no real title available?)
• scientific article; zbMATH DE number 2159644 (Why is no real title available?)
• scientific article; zbMATH DE number 2159655 (Why is no real title available?)
• Bounded-degree graphs have arbitrarily large queue-number
• Comparing Queues and Stacks As Machines for Laying Out Graphs
• Computing straight-line 3D grid drawings of graphs in linear volume
• Embedding planar graphs in four pages
• Graph layouts via layered separators
• Layered separators in minor-closed graph classes with applications
• Laying Out Graphs Using Queues
• Layout of Graphs with Bounded Tree-Width
• Mixed linear layouts of planar graphs
• On acyclic colorings of planar graphs
• On the Queue Number of Planar Graphs
• On the queue-number of graphs with bounded tree-width
• Planar graphs have bounded queue-number
• Planar graphs of bounded degree have bounded queue number
• Queue layouts of planar 3-trees
• Sorting Using Networks of Queues and Stacks
• Stacks, queues and tracks: layouts of graph subdivisions
• Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions
• Three-Dimensional Circuit Layouts
• Towards a Theory of Geometric Graphs
• Track layouts, layered path decompositions, and leveled planarity

Cited in

(14)

• Planar graphs have bounded queue-number
• An improved upper bound on the queue number of planar graphs
• Bounded-degree graphs have arbitrarily large queue-number
• Queue layouts of planar 3-trees
• Planar graphs of bounded degree have bounded queue number
• scientific article; zbMATH DE number 1954397 (Why is no real title available?)
• Stack-number is not bounded by queue-number
• Linear layouts of bipartite planar graphs
• Edge Partitions and Visibility Representations of 1-planar Graphs
• On the queue number of planar graphs
• Parameterized algorithms for queue layouts
• Parameterized Algorithms for Queue Layouts
• On the Queue Number of Planar Graphs
• The mixed page number of graphs

This page was built for publication: Planar graphs of bounded degree have bounded queue number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5235482)