TY - JOUR
AU - Angelini, Patrizio
AU - Chaplick, Steven
AU - Cornelsen, Sabine
AU - Da Lozzo, Giordano
PY - 2024/07/09
Y2 - 2024/11/08
TI - On Upward-Planar L-Drawings of Graphs
JF - Journal of Graph Algorithms and Applications
JA - JGAA
VL - 28
IS - 1
SE -
DO - 10.7155/jgaa.v28i1.2950
UR - https://jgaa.info/index.php/jgaa/article/view/2950
SP - 275-299
AB - <p>In an <em>upward-planar L-drawing</em> of a directed acyclic graph (DAG) each edge $e=(v,w)$ is represented as a polyline composed of a vertical segment with its lowest endpoint at the <em>tail</em> $v$ of $e$ and of a horizontal segment ending at the <em>head</em> $w$ of $e$. Distinct edges may overlap, but must not cross.</p><p>Recently, upward-planar L-drawings have been studied for $st$-graphs, i.e., planar DAGs with a single source $s$ and a single sink $t$ containing an edge directed from $s$ to $t$.</p><p>It is known that a<em> plane $st$-graph</em>, i.e., an embedded $st$-graph in which the edge $(s,t)$ is incident to the outer face, admits an upward-planar L-drawing if and only if it admits a bitonic $st$-ordering, which can be tested in linear time. %</p><p>We study upward-planar L-drawings of DAGs that are not necessarily $st$-graphs.</p><p>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 $st$-graph admitting a bitonic $st$-ordering.</p><p>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.</p><p>On the algorithmic side, we consider DAGs with a single source (or a single sink).</p><p>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.</p><p>For the single-sink case of (b) it even suffices that each biconnected component is series-parallel.</p>
ER -