Abstract
We introduce and study level-planar straight-line drawings with a fixed number λ
of slopes. For proper level graphs (all edges connect vertices of adjacent levels), we give an O(nlog2n/loglogn)
-time algorithm that either finds such a drawing or determines that no such drawing exists. Moreover, we consider the partial drawing extension problem, where we seek to extend an immutable drawing of a subgraph to a drawing of the whole graph, and the simultaneous drawing problem, which asks about the existence of drawings of two graphs whose restrictions to their shared subgraph coincide. We present O(n4/3logn)
-time and O(λn10/3logn)
-time algorithms for these respective problems on proper level-planar graphs. We complement these positive results by showing that testing whether non-proper level graphs admit level-planar drawings with λ
slopes is NP-hard even in restricted cases.
of slopes. For proper level graphs (all edges connect vertices of adjacent levels), we give an O(nlog2n/loglogn)
-time algorithm that either finds such a drawing or determines that no such drawing exists. Moreover, we consider the partial drawing extension problem, where we seek to extend an immutable drawing of a subgraph to a drawing of the whole graph, and the simultaneous drawing problem, which asks about the existence of drawings of two graphs whose restrictions to their shared subgraph coincide. We present O(n4/3logn)
-time and O(λn10/3logn)
-time algorithms for these respective problems on proper level-planar graphs. We complement these positive results by showing that testing whether non-proper level graphs admit level-planar drawings with λ
slopes is NP-hard even in restricted cases.
| Original language | English |
|---|---|
| Pages (from-to) | 176–196 |
| Journal | Algorithmica |
| Volume | 84 |
| DOIs | |
| Publication status | Published - 2022 |