Extending Upward Planar Graph Drawings

The UPE-FUE problem is NP-complete. (Left) An instance $(G,\ell,\prec)$ of Partial Level Planarity with a prescribed upward embedding. (Center and right) An instance $(U,H,\Gamma_H)$ of UPE-FUE equivalent to $(G,\ell,\prec)$.

Abstract

In this paper we study the computational complexity of the Upward Planarity Extension problem, which takes in input an upward planar drawing $\Gamma_H$ of a subgraph $H$ of a directed graph $G$ and asks whether $\Gamma_H$ can be extended to an upward planar drawing of $G$. Our study fits into the line of research on the extensibility of partial representations, which has recently become a mainstream in Graph Drawing.
We show the following results.

Publication
In 16th International Symposium on Algorithms and Data Structures (WADS 2019)
Avatar
Giordano Da Lozzo
Assistant Professor (RTDa)

My research interests are in Algorithm Engineering and Complexity, focused in particular on the theoretical and algorithmic challenges arising from the visualization of graphs.

Related