A Tight Subexponential-time Algorithm for Two-Page Book Embedding
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911848622718976 |
|---|---|
| author | Ganian, Robert Mueller, Haiko Ordyniak, Sebastian Paesani, Giacomo Rychlicki, Mateusz |
| author_facet | Ganian, Robert Mueller, Haiko Ordyniak, Sebastian Paesani, Giacomo Rychlicki, Mateusz |
| contents | A book embedding of a graph is a drawing that maps vertices onto a line and edges to simple pairwise non-crossing curves drawn into pages, which are half-planes bounded by that line. Two-page book embeddings, i.e., book embeddings into 2 pages, are of special importance as they are both NP-hard to compute and have specific applications. We obtain a 2^(O(\sqrt{n})) algorithm for computing a book embedding of an n-vertex graph on two pages -- a result which is asymptotically tight under the Exponential Time Hypothesis. As a key tool in our approach, we obtain a single-exponential fixed-parameter algorithm for the same problem when parameterized by the treewidth of the input graph. We conclude by establishing the fixed-parameter tractability of computing minimum-page book embeddings when parameterized by the feedback edge number, settling an open question arising from previous work on the problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_14087 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Tight Subexponential-time Algorithm for Two-Page Book Embedding Ganian, Robert Mueller, Haiko Ordyniak, Sebastian Paesani, Giacomo Rychlicki, Mateusz Data Structures and Algorithms Computational Geometry F.2; G.2 A book embedding of a graph is a drawing that maps vertices onto a line and edges to simple pairwise non-crossing curves drawn into pages, which are half-planes bounded by that line. Two-page book embeddings, i.e., book embeddings into 2 pages, are of special importance as they are both NP-hard to compute and have specific applications. We obtain a 2^(O(\sqrt{n})) algorithm for computing a book embedding of an n-vertex graph on two pages -- a result which is asymptotically tight under the Exponential Time Hypothesis. As a key tool in our approach, we obtain a single-exponential fixed-parameter algorithm for the same problem when parameterized by the treewidth of the input graph. We conclude by establishing the fixed-parameter tractability of computing minimum-page book embeddings when parameterized by the feedback edge number, settling an open question arising from previous work on the problem. |
| title | A Tight Subexponential-time Algorithm for Two-Page Book Embedding |
| topic | Data Structures and Algorithms Computational Geometry F.2; G.2 |
| url | https://arxiv.org/abs/2404.14087 |