2026/07/28 by Giordano Andreola, Susanna Caroppo, Giordano Da Lozzo +5
#cs.CG #cs.DS
The Partial Drawing Extensibility problem, for short PDE, takes as input a triple ⟨ G,H,ΓH⟩, where G is a planar graph, H is a subgraph of G, and ΓH is a straight-line planar drawing of H, and asks whether Γ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 Γ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(p2 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.