Home  Issues  About JGAA  Instructions for Authors 
Special issue on Selected papers from the Twentynineth International Symposium on Graph Drawing and Network Visualization, GD 2021
DOI: 10.7155/jgaa.00617
Upward Planar Drawings with Three and More Slopes
Vol. 27, no. 2, pp. 4970, 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 straightline 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 nonplanar setting.
Moreover, the slope number can also be defined for directed graphs and upward planar drawings.
We study upward planar straightline 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 NPhard
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 CCBY license.

Submitted: December 2021.
Reviewed: March 2022.
Revised: April 2022.
Accepted: October 2022.
Final: October 2022.
Published: February 2023.

Journal Supporters
