Upward Planar Drawings with Three and More Slopes

Jonathan Klawitter ; Johannes Zink

Journal of Graph Algorithms and Applications, Special issue on Selected papers from the Twenty-nineth International Symposium on Graph Drawing and Network Visualization, GD 2021 , Tome 27 (2023) no. 2, pp. 49-70.

Résumé

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.

Détail

DOI : 10.7155/jgaa.00617

Keywords: graph drawing, upward planar, slope number, visual complexity