PATHWIDTH AND LAYERED DRAWINGS OF TREES

DOI10.1142/S0218195904001433MaRDI QIDQ4652929zbMATH OpenFDO

Authors Matthew Suderman

Publication date 28 February 2005

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0218195904001433

zbMATH Keywords

graph drawinglayered drawingtree

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (including graph drawing) in computer science (68R10)

Review text

An \(h\)-layered drawing of a graph \(G\) is a drawing of \(G\) in the plane, in which each vertex is represented by a point on one of \(h\) parallel lines, called layers, and each edge is represented as the line segment between its endpoints. Edges whose endpoints are on the same layer are called flat, those joining points on adjacent layers are proper, and all others are said to be long. Different types of layered drawings are obtained if one forbids one or more types of the edges. In this paper, upper and lower bounds on the number of layers required by different types of layered drawings of trees are derived. In addition, linear-time algorithms are given for obtaining different types of layered drawings whose number of layers matches the derived bounds. Layered drawings of graphs have applications in optimization, visualization, DNA mapping, and VLSI layout. A survey on these is given in [\textit{P. Mutzel}, ``Optimization in leveled graphs, in: Encyclopedia of optimization, P. M. Pardalos and C. A. Floudas (eds.), Kluwer, 189--196 (2001)].

Recommendations

• Minimum-layer drawings of trees (extended abstract)
• Upward Drawings of Trees on the Minimum Number of Layers
• On the parameterized complexity of layered graph drawing
• Minimum-layer upward drawings of trees
• Order-preserving drawings of trees with approximately optimal height (and small width)

Cites work

• Drawing graphs on two and three lines
• Drawing graphs. Methods and models
• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 49142 (Why is no real title available?)
• Interval graphs and maps of DNA
• The vertex separation and search number of a graph

Cited in

(26)

• Anagram-free graph colouring
• Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem
• Horton-Strahler number, rooted pathwidth and upward drawings of trees
• Graph drawings with few slopes
• \(k\)-spine, 1-bend planarity
• Triangulating planar graphs while keeping the pathwidth small
• Minimum-layer drawings of trees (extended abstract)
• Proximity drawings of high-degree trees
• Straight-line drawings of outerplanar graphs in \(O(dn \log n)\) area
• Drawing Halin-graphs with small height
• On Layered Fan-Planar Graph Drawings
• Two results on layered pathwidth and linear layouts
• Order-preserving drawings of trees with approximately optimal height (and small width)
• A Lower Bound on the Area Requirements of Series-Parallel Graphs
• Upward Drawings of Trees on the Minimum Number of Layers
• Drawing Planar Graphs with Reduced Height
• Separating layered treewidth and row treewidth
• 2-Layer Graph Drawings with Bounded Pathwidth
• Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs
• Faster algorithms for grid and layered drawings of plane 3-trees
• Forbidden patterns in mixed linear layouts
• Layered polyline drawings of planar graphs
• 2-connecting outerplanar graphs without blowing up the pathwidth
• On the stab number of rectangle intersection graphs
• Convergence of Newton's method over commutative semirings
• On the parameterized complexity of layered graph drawing

This page was built for publication: PATHWIDTH AND LAYERED DRAWINGS OF TREES

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4652929)