Planar graphs of bounded degree have bounded queue number

DOI10.1137/19M125340XzbMATH Open1423.05049arXiv1811.00816OpenAlexW2977420014WikidataQ127173129 ScholiaQ127173129MaRDI QIDQ5235482FDOQ5235482

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)

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.

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

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

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)

Cites Work

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

Cited In (14)

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

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)