A Fixed-Parameter Algorithm for Extending Upward Planar Drawings

Abstract

An upward planar drawing of a directed acyclic graph is a planar drawing where every edge is pointed upward from its tail to head. Upward planar drawings are among the most natural drawing styles of directed graphs and have been researched in a variety of different settings, recently including that of drawing extension. In the drawing extension setting, one asks: given a graph $G$ and a (typically connected) subgraph $H$ of $G$ with a drawing $\Gamma(H)$, can we complete $\Gamma(H)$ to a drawing of $G$? Drawing extension problems have been studied for numerous drawing styles; the vast majority of these are NP-hard and a typical approach aimed at circumventing their intractability is to design parameterized algorithms where the parameter measures"how much"of $G$ is still missing from the pre-drawn graph $H$. Most algorithms obtained within this framework require only a small number of edges to be missing from $H$ in order to remain efficient. In this article, we present a fixed-parameter algorithm for extending upward planar drawings which overcomes this drawback by using the $\textit{vertex+edge deletion distance}$ as the parameter, thus achieving tractability even for instances with many missing edges. A key ingredient towards our result is a novel characterization of"canonical"sets of missing edges which cross a horizontal line segment in the drawing.