2026-07-22T11:01:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20211 2024-07-02T07:52:51Z ddc:004 open_access

A Tight Subexponential-Time Algorithm for Two-Page Book Embedding Ganian, Robert Müller, Haiko Ordyniak, Sebastian Paesani, Giacomo Rychlicki, Mateusz book embedding page number subexponential algorithms subhamiltonicity feedback edge number 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^𝒪(√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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Robert Ganian and Haiko Müller and Sebastian Ordyniak and Giacomo Paesani and Mateusz Rychlicki 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.68 urn:nbn:de:0030-drops-202114 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.68 eng https://creativecommons.org/licenses/by/4.0/legalcode