Layout of Graphs with Bounded Tree-Width

DOI10.1137/S0097539702416141zbMath1069.05055OpenAlexW2124498152WikidataQ61067897 ScholiaQ61067897MaRDI QIDQ5317164

David R. Wood, Pat Morin, Vida Dujmović

Publication date: 16 September 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

acyclic chromatic numberacyclic coloringthree-dimensional graph drawingqueue layouttrack-numbertree-partitionqueue-numbertrack layouttree-partition-width

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (48)

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 ⋮ Stack-number is not bounded by queue-number ⋮ On the queue number of planar graphs ⋮ Computing straight-line 3D grid drawings of graphs in linear volume ⋮ Acyclic coloring of graphs with maximum degree 7 ⋮ Layered separators in minor-closed graph classes with applications ⋮ Queue layouts of iterated line directed graphs ⋮ Acyclic coloring with few division vertices ⋮ Acyclic colorings of graph subdivisions revisited ⋮ Crossings in grid drawings ⋮ 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 ⋮ Drawing Graphs on Few Lines and Few Planes ⋮ Track Layout Is Hard ⋮ Stack and Queue Layouts via Layered Separators ⋮ Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs ⋮ Linear layouts of bipartite planar graphs ⋮ 2-Layer Graph Drawings with Bounded Pathwidth ⋮ Improved Bounds for Track Numbers of Planar Graphs ⋮ Local and union boxicity ⋮ Parameters Tied to Treewidth ⋮ Minor-Closed Graph Classes with Bounded Layered Pathwidth ⋮ Graph layouts via layered separators ⋮ Characterisations and examples of graph classes with bounded expansion ⋮ Two Results on Layered Pathwidth and Linear Layouts ⋮ Track layouts, layered path decompositions, and leveled planarity ⋮ On the queue-number of graphs with bounded tree-width ⋮ Improved Bounds for Centered Colorings ⋮ On the parameterized complexity of layered graph drawing ⋮ Acyclically 3-colorable planar graphs ⋮ A new upper bound on the queuenumber of hypercubes ⋮ 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 ⋮ Acyclic 3-coloring of generalized Petersen graphs ⋮ Volume requirements of 3D upward drawings ⋮ On the upward book thickness problem: combinatorial and complexity results ⋮ On tree-partition-width ⋮ On acyclically 4-colorable maximal planar graphs ⋮ Planar Graphs of Bounded Degree Have Bounded Queue Number ⋮ The Local Queue Number of Graphs with Bounded Treewidth ⋮ Parameterized Algorithms for Queue Layouts

This page was built for publication: Layout of Graphs with Bounded Tree-Width