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

arXiv (Cornell University)

Abstract

Given a planar graph, a subset of its vertices called terminals, and $k \in \mathbb{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~\cite{GarneroST17}. 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.

Authors 3

1. Thekla Hamm

   Eindhoven University of Technology

   Affiliation as printed

   TU Eindhoven

2. Sukanya Pandey Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen

3. Krisztina Szilágyi

   Czech Technical University in Prague

   Affiliation as printed

   Czech Technical University in Prague