Special issue on Selected papers from the Twenty-nineth International Symposium on Graph Drawing and Network Visualization, GD 2021
Upward Planar Drawings with Three and More Slopes
Vol. 27, no. 2, pp. 49-70, 2023. Regular paper.
Abstract The slope number of a graph $G$ is the smallest number of slopes needed for the segments representing the edges in any straight-line drawing of $G$. It serves as a measure of the visual complexity of a graph drawing. Several bounds on the slope number for particular graph classes have been established, both in the planar and the non-planar setting. Moreover, the slope number can also be defined for directed graphs and upward planar drawings. We study upward planar straight-line drawings that use only a constant number of slopes. In particular, for a fixed number $k$ of slopes, we are interested in whether a given directed graph $G$ with maximum in- and outdegree at most $k$ admits an upward planar $k$-slope drawing. We investigate this question both in the fixed and the variable embedding scenario. We show that this problem is in general NP-hard to decide for outerplanar graphs ($k = 3$) and planar graphs ($k \ge 3$). On the positive side, we can decide whether a given cactus graph admits an upward planar $k$-slope drawing and, in the affirmative, construct such a drawing in FPT time with parameter $k$. Furthermore, we can determine the minimum number of slopes required for a given tree in linear time and compute the corresponding drawing efficiently.

 This work is licensed under the terms of the CC-BY license.
Submitted: December 2021.
Reviewed: March 2022.
Revised: April 2022.
Accepted: October 2022.
Final: October 2022.
Published: February 2023.
Communicated by Ignaz Rutter and Helene Purchase
article (PDF)