On Upward-Planar L-Drawings of Graphs

Authors

  • Patrizio Angelini John Cabot University
  • Steven Chaplick Maastricht University
  • Sabine Cornelsen University of Konstanz
  • Giordano Da Lozzo Roma Tre University

DOI:

https://doi.org/10.7155/jgaa.v28i1.2950

Keywords:

planar L-drawings, upward planarity, bitonic st-ordering

Abstract

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.

Downloads

Downloads

Published

2024-07-09

How to Cite

Angelini, P., Chaplick, S., Cornelsen, S., & Da Lozzo, G. (2024). On Upward-Planar L-Drawings of Graphs. Journal of Graph Algorithms and Applications, 28(1), 275–299. https://doi.org/10.7155/jgaa.v28i1.2950

Issue

Section

Articles

Categories