Comparing Queues and Stacks As Machines for Laying Out Graphs

DOI10.1137/0405031zbMath0764.05093WikidataQ61067912 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 embedding; graph embedding; linear order; queue layout; stack layout; queuenumber; stacknumber; ternary hypercube

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

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

05C99: Graph theory

94C15: Applications of graph theory to circuits and networks

Related Items

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