Extending Biconnected Straight-Line Planar Drawings

Abstract

The Partial Drawing Extensibility problem, for short PDE, takes as input a triple $⟨G,H,\hat{I}{“}_H⟩$, where $G$ is a planar graph, $H$ is a subgraph of $G$, and $\hat{I}{“}_H$ is a straight-line planar drawing of $H$, and asks whether $\hat{I}{“}_H$ can be extended to a straight-line planar drawing of $G$. Patrignani [Int. J. Found. Comput. Sci. (2006)] proved that the PDE problem is NP-hard, exploiting instances in which $H$ is highly disconnected. In this paper, we study the PDE problem under the requirement that the initial partial drawing $\hat{I}{“}_H$ is biconnected. We show that PDE remains NP-hard even for instances in which $H$ is a biconnected graph with faces of bounded size, $G$ is subcubic, and the part of $G$ that is not in $H$ consists of length-$2$ paths. The complexity of PDE remains however open when $H$ is connected (or even biconnected) if $G$ has a fixed embedding. In this setting both a polynomial-time algorithm or an NP-hardness proof seem to be elusive targets. As a step towards tackling this problem, we study instances of PDE in which $H$ is biconnected, $G$ has a fixed embedding, and the rest of the graph consists of $p$ length-2 paths, and present an $O(p^{2}n)$-time algorithm, a result in sharp contrast with the NP-hardness of the variable embedding setting. Moreover, with an approach based on the Existential Theory of the Reals, we show that, if $H$ is biconnected, the problem is FPT parameterized by the vertex cover number of $G$, both in a fixed and in a variable embedding setting.

Appears in the Proceedings of the 34th International Symposium on Graph Drawing and Network Visualization

Topics & keywords