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

Given a planar graph, a subset of its vertices called terminals, and \(k \in N\), the 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. In this paper, we present the first polynomial kernel for 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. This is joint work with Thekla Hamm and Sukanya Pandey.