@article{Angelini_Chaplick_Cornelsen_Da Lozzo_2024, title={On Upward-Planar L-Drawings of Graphs}, volume={28}, url={https://jgaa.info/index.php/jgaa/article/view/2950}, DOI={10.7155/jgaa.v28i1.2950}, abstractNote={<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>}, number={1}, journal={Journal of Graph Algorithms and Applications}, author={Angelini, Patrizio and Chaplick, Steven and Cornelsen, Sabine and Da Lozzo, Giordano}, year={2024}, month={Jul.}, pages={275–299} }