A Polynomial Kernel for Face-Cover on Non-Embedded Planar Graphs

Abstract Given a planar graph, a subset of its vertices called terminals, and \(k \in \mathbb{N}\), the \textsc{Face Cover Number} problem asks whether the terminals lie on the boundaries of at most $k$ faces of some embedding of the input graph. When a plane graph is given in the input, the problem is known to have a polynomial kernel~\cite{GarneroST17}. In this paper, we present the first polynomial kernel for \textsc{Face Cover Number} when the input is a planar graph (without a fixed embedding). Our approach overcomes the challenge of not having a predefined set of face boundaries by building a kernel bottom-up on an SPR-tree while preserving the essential properties of the face cover along the way.