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

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