2026-08-03T23:35:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16808 2024-03-06T10:58:23Z ddc:004 open_access

On Upward-Planar L-Drawings of Graphs Angelini, Patrizio Chaplick, Steven Cornelsen, Sabine Da Lozzo, Giordano graph drawing planar L-drawings directed graphs bitonic st-ordering upward planarity series-parallel graphs In an upward-planar L-drawing of a directed acyclic graph (DAG) each edge e is represented as a polyline composed of a vertical segment with its lowest endpoint at the tail of e and of a horizontal segment ending at the head of e. Distinct edges may overlap, but 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. On the combinatorial side, 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 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: (i) when the drawing must respect a prescribed embedding and (ii) when no restriction is given on the embedding, but the DAG is biconnected and series-parallel. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Patrizio Angelini and Steven Chaplick and Sabine Cornelsen and Giordano Da Lozzo 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.10 urn:nbn:de:0030-drops-168085 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.10 eng https://creativecommons.org/licenses/by/4.0/legalcode