Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00587
Upward planar drawings with two slopes
Jonathan Klawitter and
Tamara Mchedlidze
Vol. 26, no. 1, pp. 171-198, 2022. Regular paper.
Abstract In an upward planar 2-slope drawing of a digraph,
edges are drawn as straight-line segments in the upward direction
without crossings using only two different slopes.
We investigate whether a given upward planar digraph admits such a drawing
and, if so, how to construct it.
For the fixed embedding scenario, we give a simple characterisation
and a linear-time construction by adopting algorithms from orthogonal drawings.
For the variable embedding scenario, we describe a linear-time algorithm for single-source digraphs,
a quartic-time algorithm for series-parallel digraphs,
and a fixed-parameter tractable algorithm for general digraphs.
For the latter two classes, we make use of SPQR-trees and the notion of upward spirality.
As an application of this drawing style,
we show how to draw an upward planar phylogenetic network with two slopes
such that all leaves lie on a horizontal line.
This work is licensed under the terms of the CC-BY license.
|
Submitted: November 2021.
Reviewed: March 2022.
Revised: April 2022.
Accepted: May 2022.
Final: May 2022.
Published: June 2022.
Communicated by
Giuseppe Liotta
|
Journal Supporters
|