Laying Out Graphs Using Queues
From MaRDI portal
Publication:4015976
DOI10.1137/0221055zbMath0778.05078OpenAlexW1987216097WikidataQ29041710 ScholiaQ29041710MaRDI QIDQ4015976
Arnold L. Rosenberg, Lenwood S. Heath
Publication date: 6 December 1992
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0221055
Analysis of algorithms and problem complexity (68Q25) 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) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Outer 1-planar graphs ⋮ Parameterized Algorithms for Queue Layouts ⋮ An improved upper bound on the queue number of the hypercube ⋮ (3,2)-Track Layout of Bipartite Graph Subdivisions ⋮ An approach to emulating separable graphs ⋮ 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 ⋮ Parameterized analysis and crossing minimization problems ⋮ Layered separators in minor-closed graph classes with applications ⋮ Queue layouts of iterated line directed graphs ⋮ Separating layered treewidth and row treewidth ⋮ Stack and queue number of 2-trees ⋮ 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 ⋮ Track Layout Is Hard ⋮ Linear layouts of bipartite planar graphs ⋮ Improved Bounds for Track Numbers of Planar Graphs ⋮ Line and plane cover numbers revisited ⋮ Mixed linear layouts: complexity, heuristics, and experiments ⋮ Homotopy height, grid-major height and graph-drawing height ⋮ Geometric thickness in a grid ⋮ Lazy queue layouts of posets ⋮ The biplanar tree graph ⋮ Characterization of unlabeled level planar trees ⋮ 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 ⋮ Two Results on Layered Pathwidth and Linear Layouts ⋮ Data Structures and their Planar Graph Layouts ⋮ Track layouts, layered path decompositions, and leveled planarity ⋮ Planar lattices are lexicographically shellable ⋮ On the queue-number of graphs with bounded tree-width ⋮ On the parameterized complexity of layered graph drawing ⋮ Acyclically 3-colorable planar graphs ⋮ A new upper bound on the queuenumber of hypercubes ⋮ The pagenumber of \(k\)-trees is \(O(k)\) ⋮ Unnamed Item ⋮ Processor-efficient sparse matrix-vector multiplication ⋮ A note on ``An improved upper bound on the queue number of the hypercube ⋮ Curve-constrained drawings of planar graphs ⋮ 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 ⋮ Queue layouts of planar 3-trees ⋮ On the Hardness and Inapproximability of Recognizing Wheeler Graphs ⋮ On Layered Fan-Planar Graph Drawings ⋮ Planar Graphs of Bounded Degree Have Bounded Queue Number ⋮ Characterizations of Deque and Queue Graphs ⋮ Multilevel Planarity ⋮ On mixed linear layouts of series-parallel graphs ⋮ Graph Classes and Forbidden Patterns on Three Vertices ⋮ 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 the complexity of recognizing Wheeler graphs
