Loading...
On Upward-Planar L-Drawings of Graphs
Angelini, Patrizio
Chaplick, Steven Cornelsen, Sabine Da Lozzo, Giordano
Chaplick, Steven
Cornelsen, Sabine
Da Lozzo, Giordano
Citations
Altmetric:
Abstract
In anupward-planar L-drawingof a directed acyclic graph (DAG)each edgee= (v,w) is represented as a polyline composed of a vertical segment with itslowest endpoint at thetailvofeand of a horizontal segment ending at theheadwofe.Distinct edges may overlap, but must not cross. Recently, upward-planar L-drawingshave been studied forst-graphs, i.e., planar DAGs with a single sourcesand a singlesinktcontaining an edge directed fromstot. It is known that aplanest-graph, i.e.,an embeddedst-graph in which the edge (s,t) is incident to the outer face, admits anupward-planar L-drawing if and only if it admits a bitonicst-ordering, which can betested in linear time.We study upward-planar L-drawings of DAGs that are not necessarilyst-graphs. Asa combinatorial result, we show that a plane DAG admits an upward-planar L-drawingif and only if it is a subgraph of a planest-graph admitting a bitonicst-ordering.This allows us to show that not every tree with a fixed bimodal embedding admits anupward-planar L-drawing. Moreover, we prove that any directed acyclic cactus witha single source (or a single sink) admits an upward-planar L-drawing, which respectsa given outerplanar embedding if there are no transitive edges. On the algorithmicside, we consider DAGs with a single source (or a single sink). We give linear-timetesting algorithms for these DAGs in two cases: (a) when the drawing must respect aprescribed embedding and (b) when no restriction is given on the embedding, but theunderlying undirected graph is series-parallel. For the single-sink case of (b) it evensuffices that each biconnected component is series-parallel.
Description
Date
2024
Journal Title
Journal ISSN
Volume Title
Publisher
Research Projects
Organizational Units
Journal Issue
Keywords
Planar L-drawings, Upward planarity, Bitonic st-ordering
Citation
Angelini, Patrizio, Steven Chaplick, Sabine Cornelsen, and Giordano Da Lozzo. “On Upward-Planar L-Drawings of Graphs.” Journal of Graph Algorithms and Applications 28 (1): 275–99. 2024.