Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00432
Ideal Drawings of Rooted Trees With Approximately Optimal Width
Vol. 21, no. 4, pp. 631-648, 2017. Regular paper.
Abstract For rooted trees, an ideal drawing is one that is planar,
straight-line, strictly-upward, and order-preserving.
This paper considers ideal drawings of rooted trees with the objective
of keeping the width of such drawings small. It is not known
whether finding the minimum width is NP-hard or polynomial.
This paper gives a 2-approximation for this problem, and a
$2\Delta$-approximation
(for $\Delta$-ary trees) where additionally the height is $O(n)$.
For trees with $\Delta\leq 3$, the former algorithm finds ideal drawings with
minimum width.
|
Submitted: August 2016.
Reviewed: January 2017.
Revised: February 2017.
Accepted: April 2017.
Final: April 2017.
Published: April 2017.
Communicated by
Giuseppe Liotta
|
Journal Supporters
|