A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912808178810880 |
|---|---|
| author | Hamm, Thekla Pandey, Sukanya Szilágyi, Krisztina |
| author_facet | Hamm, Thekla Pandey, Sukanya Szilágyi, Krisztina |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_04169 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs Hamm, Thekla Pandey, Sukanya Szilágyi, Krisztina Data Structures and Algorithms Computational Complexity Discrete Mathematics 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. |
| title | A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs |
| topic | Data Structures and Algorithms Computational Complexity Discrete Mathematics |
| url | https://arxiv.org/abs/2601.04169 |