Planar Graphs of Bounded Degree Have Bounded Queue Number

DOI10.1137/19M125340XzbMath1423.05049arXiv1811.00816OpenAlexW2977420014WikidataQ127173129 ScholiaQ127173129MaRDI QIDQ5235482

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

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

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

Related Items (9)

Parameterized Algorithms for Queue Layouts ⋮ Stack-number is not bounded by queue-number ⋮ On the queue number of planar graphs ⋮ The mixed page number of graphs ⋮ An improved upper bound on the queue number of planar graphs ⋮ Linear layouts of bipartite planar graphs ⋮ Queue layouts of planar 3-trees ⋮ Edge Partitions and Visibility Representations of 1-planar Graphs ⋮ Parameterized Algorithms for Queue Layouts

Cites Work

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

This page was built for publication: Planar Graphs of Bounded Degree Have Bounded Queue Number