Stack-number is not bounded by queue-number
From MaRDI portal
Publication:2151179
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
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
