Ignaz Rutter

Giordano Da Lozzo, Fabrizio Frati, Ignaz Rutter

In 1999, Heath, Pemmaraju, and Trenk [SIAM J. Comput. 28(4), 1999] extended the classic notion of book embeddings to digraphs, introducing the concept of upward book embeddings, in which the vertices must appear along the spine in a topological order and the edges are partitioned into pages, so that no two edges in the same page cross. For a partitioned digraph $G=(V,\bigcup^k_{i=1} E_i)$, that is, a digraph whose edge set is partitioned into $k$ subsets, an upward book embedding is required to assign edges to pages as prescribed by the given partition. In a companion paper, Heath and Pemmaraju [SIAM J. Comput 28(5), 1999] proved that the problem of testing the existence of an upward book embedding of a partitioned digraph is linear-time solvable for $k=1$ and recently Akitaya, Demaine, Hesterberg, and Liu [GD, 2017] have shown the problem NP-complete for $k\geq 3$. In this paper, we study upward book embeddings of partitioned digraphs and focus on the unsolved case $k=2$. Our first main result is a novel characterization of the upward embeddings that support an upward book embedding in two pages. We exploit this characterization in several ways, and obtain a rich picture of the complexity landscape of the problem. First, we show that the problem remains NP-complete when $k=2$, thus closing the complexity gap for the problem. Second, we show that, for an $n$-vertex partitioned digraph $G$ with a prescribed planar embedding, the existence of an upward book embedding of $G$ that respects the given planar embedding can be tested in $O(n \log^3 n)$ time. Finally, leveraging the SPQ(R)-tree decomposition of biconnected graphs into triconnected components, we present a cubic-time testing algorithm for biconnected directed partial $2$-trees.

Patrizio Angelini, Sabine Cornelsen, Giordano Da Lozzo et al.

We consider upward-planar layered drawings of directed graphs, i.e., crossing-free drawings in which each edge is drawn as a y-monotone curve going upward from its tail to its head, and the y-coordinates of the vertices are integers. The span of an edge in such a drawing is the absolute difference between the y-coordinates of its endpoints, and the span of the drawing is the maximum span of any edge. The span of an upward-planar graph is the minimum span over all its upward-planar drawings. We study the problem of determining the span of upward-planar graphs and provide both combinatorial and algorithmic results. On the combinatorial side, we present upper and lower bounds for the span of directed trees. On the algorithmic side, we show that the problem of determining the span of an upward-planar graph is NP-complete already for directed trees and for biconnected single-source graphs. Moreover, we give efficient algorithms for several graph families with a bounded number of sources, including st-planar graphs and graphs where the planar or upward-planar embedding is prescribed. Furthermore, we show that the problem is fixed-parameter tractable with respect to the vertex cover number and the treedepth plus the span.

Helen Purchase, Ignaz Rutter

This is the arXiv index for the electronic proceedings of GD 2021, which contains the peer-reviewed and revised accepted papers with an optional appendix. Proceedings (without appendices) are also to be published by Springer in the Lecture Notes in Computer Science series.

Thomas Leibfried, Tamara Mchedlidze, Nico Meyer-Hübner et al.

Future power grids will offer enhanced controllability due to the increased availability of power flow control units (FACTS). As the installation of control units in the grid is an expensive investment, we are interested in using few controllers to achieve high controllability. In particular, two questions arise: How many flow control buses are necessary to obtain globally optimal power flows? And if fewer flow control buses are available, what can we achieve with them? Using steady state IEEE benchmark data sets, we explore experimentally that already a small number of controllers placed at certain grid buses suffices to achieve globally optimal power flows. We present a graph-theoretic explanation for this behavior. To answer the second question we perform a set of experiments that explore the existence and costs of feasible power flow solutions at increased loads with respect to the number of flow control buses in the grid. We observe that adding a small number of flow control buses reduces the flow costs and extends the existence of feasible solutions at increased load.