Home | Issues | About JGAA | Instructions for Authors |
Special issue on Selected papers from the Twenty-nineth 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. 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.
|
Journal Supporters
|