Comparing Queues and Stacks As Machines for Laying Out Graphs

DOI10.1137/0405031zbMath0764.05093OpenAlexW1970144066WikidataQ61067912 ScholiaQ61067912MaRDI QIDQ4018851

Arnold L. Rosenberg, Lenwood S. Heath, Frank Thompson Leighton

Publication date: 16 January 1993

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0405031

zbMATH Keywords

book embeddinggraph embeddinglinear orderqueue layoutstack layoutqueuenumberstacknumberternary hypercube

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (05C99) Applications of graph theory to circuits and networks (94C15)

Related Items (58)

Parameterized Algorithms for Queue Layouts ⋮ (3,2)-Track Layout of Bipartite Graph Subdivisions ⋮ Parameterized algorithms for linear layouts of graphs with respect to the vertex cover number ⋮ Stack-number is not bounded by queue-number ⋮ On the queue-number of partial orders ⋮ Linear layouts of complete graphs ⋮ On the queue number of planar graphs ⋮ Computing straight-line 3D grid drawings of graphs in linear volume ⋮ The mixed page number of graphs ⋮ A fast algorithm for the product structure of planar graphs ⋮ Layered separators in minor-closed graph classes with applications ⋮ Queue layouts of iterated line directed graphs ⋮ RNA structures with pseudo-knots: graph-theoretical, combinatorial, and statistical properties ⋮ On the Page Number of Upward Planar Directed Acyclic Graphs ⋮ Separating layered treewidth and row treewidth ⋮ Upward book embeddability of \(st\)-graphs: complexity and algorithms ⋮ The Rique-number of graphs ⋮ Topological Graph Layouts into a Triangular Prism ⋮ Shallow Minors, Graph Products, and Beyond-Planar Graphs ⋮ An improved upper bound on the queue number of planar graphs ⋮ Graph product structure for non-minor-closed classes ⋮ Linear layouts of bipartite planar graphs ⋮ Graph theory. Abstracts from the workshop held January 2--8, 2022 ⋮ Mixed linear layouts: complexity, heuristics, and experiments ⋮ Lazy queue layouts of posets ⋮ The biplanar tree graph ⋮ Mixed Linear Layouts of Planar Graphs ⋮ Upward Partitioned Book Embeddings ⋮ The queue-number of posets of bounded width or height ⋮ Graph layouts via layered separators ⋮ Characterisations and examples of graph classes with bounded expansion ⋮ Data Structures and their Planar Graph Layouts ⋮ On the queue-number of graphs with bounded tree-width ⋮ Acyclically 3-colorable planar graphs ⋮ A new upper bound on the queuenumber of hypercubes ⋮ Unnamed Item ⋮ Processor-efficient sparse matrix-vector multiplication ⋮ Curve-constrained drawings of planar graphs ⋮ On dispersable book embeddings ⋮ Layouts of Expander Graphs ⋮ Upward three-dimensional grid drawings of graphs ⋮ Upper bounds on the queue number of \(k\)-ary \(n\)-cubes ⋮ Queue layouts of planar 3-trees ⋮ Book embedding of complex network with community structure ⋮ Queue layouts of planar 3-trees ⋮ On the upward book thickness problem: combinatorial and complexity results ⋮ Notes on graph product structure theory ⋮ Upward Book Embeddings of st-Graphs ⋮ Planar Graphs of Bounded Degree Have Bounded Queue Number ⋮ Characterizations of Deque and Queue Graphs ⋮ On mixed linear layouts of series-parallel graphs ⋮ Graph Classes and Forbidden Patterns on Three Vertices ⋮ On off-diagonal ordered Ramsey numbers of nested matchings ⋮ The Local Queue Number of Graphs with Bounded Treewidth ⋮ Parameterized Algorithms for Queue Layouts ⋮ Lazy Queue Layouts of Posets ⋮ On Mixed Linear Layouts of Series-Parallel Graphs ⋮ On dispersability of some products of cycles

This page was built for publication: Comparing Queues and Stacks As Machines for Laying Out Graphs