Geodesic
On Upward-Planar L-Drawings of Graphs
Patrizio Angelini1 ; Steven Chaplick2 ; Sabine Cornelsen3 ; Giordano Da Lozzo4
1 John Cabot University
2 Maastricht University
3 University of Konstanz
4 Roma Tre University
Journal of Graph Algorithms and Applications, Tome 28 (2024) no. 1, pp. 275-299.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

In an upward-planar L-drawing 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 tail $v$ of $e$ and of a horizontal segment ending at the head $w$ of $e$. Distinct edges may overlap, but must not cross. 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$. It is known that a plane $st$-graph, 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. % We study upward-planar L-drawings of DAGs that are not necessarily $st$-graphs. 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. 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.
DOI : 10.7155/jgaa.v28i1.2950
Keywords: planar L-drawings, upward planarity, bitonic st-ordering

Patrizio Angelini 1 ; Steven Chaplick 2 ; Sabine Cornelsen 3 ; Giordano Da Lozzo 4

1 John Cabot University
2 Maastricht University
3 University of Konstanz
4 Roma Tre University 
@article{JGAA_2024_28_1_a10,
     author = {Patrizio Angelini and Steven Chaplick and Sabine Cornelsen and Giordano Da Lozzo},
     title = {On {Upward-Planar} {L-Drawings} of {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {275--299},
     publisher = {mathdoc},
     volume = {28},
     number = {1},
     year = {2024},
     doi = {10.7155/jgaa.v28i1.2950},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2950/}
}
TY  - JOUR
AU  - Patrizio Angelini
AU  - Steven Chaplick
AU  - Sabine Cornelsen
AU  - Giordano Da Lozzo
TI  - On Upward-Planar L-Drawings of Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2024
SP  - 275
EP  - 299
VL  - 28
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2950/
DO  - 10.7155/jgaa.v28i1.2950
LA  - en
ID  - JGAA_2024_28_1_a10
ER  - 
%0 Journal Article
%A Patrizio Angelini
%A Steven Chaplick
%A Sabine Cornelsen
%A Giordano Da Lozzo
%T On Upward-Planar L-Drawings of Graphs
%J Journal of Graph Algorithms and Applications
%D 2024
%P 275-299
%V 28
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2950/
%R 10.7155/jgaa.v28i1.2950
%G en
%F JGAA_2024_28_1_a10
Patrizio Angelini; Steven Chaplick; Sabine Cornelsen; Giordano Da Lozzo. On Upward-Planar L-Drawings of Graphs. Journal of Graph Algorithms and Applications, Tome 28 (2024) no. 1, pp. 275-299. doi : 10.7155/jgaa.v28i1.2950. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2950/

Cité par Sources :