Stack-number is not bounded by queue-number

DOI10.1007/s00493-021-4585-7OpenAlexW3197365912MaRDI QIDQ2151179

David Eppstein, Pat Morin, Robert Hickingbotham, David R. Wood, Vida Dujmović

Publication date: 30 June 2022

Published in: Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

queue-numberstack-number

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (5)

Upward book embeddability of \(st\)-graphs: complexity and algorithms ⋮ Graphs of linear growth have bounded treewidth ⋮ Shallow Minors, Graph Products, and Beyond-Planar Graphs ⋮ Linear layouts of bipartite planar graphs ⋮ Treewidth, Circle Graphs, and Circular Drawings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Expansion in SL\(_2(\mathbb R)\) and monotone expanders
• Sparsity. Graphs, structures, and algorithms
• Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph
• Characterisations and examples of graph classes with bounded expansion
• RNA structures with pseudo-knots: graph-theoretical, combinatorial, and statistical properties
• Expanders and dimensional expansion
• Embedding planar graphs in four pages
• The book thickness of a graph
• Notes on graph product structure theory
• Planar graphs that need four pages
• On 3-pushdown graphs with large separators
• Graph treewidth and geometric thickness parameters
• Layered separators in minor-closed graph classes with applications
• Layouts of Expander Graphs
• The Game of Hex and the Brouwer Fixed-Point Theorem
• Laying Out Graphs Using Queues
• Comparing Queues and Stacks As Machines for Laying Out Graphs
• Graphs with E Edges Have Pagenumber O(√E)
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• The book crossing number of a graph
• Twin-width I: Tractable FO Model Checking
• Improved Bounds for Track Numbers of Planar Graphs
• Four pages are indeed necessary for planar 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
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Stack-number is not bounded by queue-number