Fabrizio Frati

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.

Fabrizio Frati, Kwan-Liu Ma

This is the arXiv index for the electronic proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017), which was held in Boston, U.S.A., September 25-27 2017. It contains the peer-reviewed and revised accepted papers with an optional appendix.