An improved upper bound on the queue number of planar graphs

DOI10.1007/S00453-022-01037-4MaRDI QIDQ2684487zbMATH OpenOpenAlexFDO

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

Publication date 16 February 2023

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-022-01037-4

zbMATH Keywords

linear layoutsplanar graphsqueue number

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Queue layouts of planar 3-trees
• Queue layouts of planar 3-trees
• On the Queue Number of Planar Graphs
• Laying Out Graphs Using Queues
• Planar graphs of bounded degree have bounded queue number

Cites work

• Comparing Queues and Stacks As Machines for Laying Out Graphs
• Embedding planar graphs in four pages
• Four pages are indeed necessary for planar graphs
• scientific article; zbMATH DE number 1954397 (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?)
• Laying Out Graphs Using Queues
• Layout of Graphs with Bounded Tree-Width
• On bandwidth, cutwidth, and quotient graphs
• On minimum cuts and the linear arrangement problem
• 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
• The bandwidth problem for graphs and matrices—a survey
• The book thickness of a graph
• Track layouts, layered path decompositions, and leveled planarity

Cited in

(14)

• On mixed linear layouts of series-parallel graphs
• Stack-number is not bounded by queue-number
• On the queue number of planar graphs
• Mixed linear layouts of planar graphs
• scientific article; zbMATH DE number 2159644 (Why is no real title available?)
• Parameterized algorithms for queue layouts
• Planar graphs of bounded degree have bounded queue number
• On the Queue Number of Planar Graphs
• Queue layouts of planar 3-trees
• Queue layouts of planar 3-trees
• Shallow Minors, Graph Products, and Beyond-Planar Graphs
• Linear layouts of bipartite planar graphs
• A new upper bound on the queuenumber of hypercubes
• Upper bounds on the queue number of \(k\)-ary \(n\)-cubes

This page was built for publication: An improved upper bound on the queue number of planar graphs

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