A Tight Subexponential-time Algorithm for Two-Page Book Embedding

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 c...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-04
Main Authors: Ganian, Robert, Mueller, Haiko, Ordyniak, Sebastian, Paesani, Giacomo, Rychlicki, Mateusz
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Computation
Embedding
Graph theory
Half planes
Parameterization
Parameters
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422