On Upward-Planar L-Drawings of Graphs
DOI:
https://doi.org/10.7155/jgaa.v28i1.2950Keywords:
planar L-drawings, upward planarity, bitonic st-orderingAbstract
In an upward-planar L-drawing of a directed acyclic graph (DAG) each edge
Recently, upward-planar L-drawings have been studied for
It is known that a plane
We study upward-planar L-drawings of DAGs that are not necessarily
As a combinatorial result, we show that a plane DAG admits an upward-planar L-drawing if and only if it is a subgraph of a plane
This allows us to show that not every tree with a fixed bimodal embedding admits an upward-planar L-drawing. Moreover, we prove that any directed acyclic cactus with a single source (or a single sink) admits an upward-planar L-drawing, which respects a given outerplanar~embedding if there are no transitive edges.
On the algorithmic side, we consider DAGs with a single source (or a single sink).
We give linear-time testing algorithms for these DAGs in two cases: (a) when the drawing must respect a prescribed embedding and (b) when no restriction is given on the embedding, but the underlying undirected graph is series-parallel.
For the single-sink case of (b) it even suffices that each biconnected component is series-parallel.
Downloads
Downloads
Published
How to Cite
License
Copyright (c) 2024 Patrizio Angelini, Steven Chaplick, Sabine Cornelsen, Giordano Da Lozzo

This work is licensed under a Creative Commons Attribution 4.0 International License.