Parameterized Algorithms for Book Embedding Problems
Journal of Graph Algorithms and Applications · 01.12.2020 · 24 (4) · 603-620
DOI: 10.7155/jgaa.00526 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Algorithms and Applications, online erschienen am 01.12.2020. Verfasst von Sujoy Bhore und 3 weiteren Autor:innen. Die Arbeit wurde bisher 20-mal zitiert (Crossref). Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
A $k$-page book embedding of a graph $G$ draws the vertices of $G$ on a line and the edges on $k$ half-planes (called pages) bounded by this line, such that no two edges on the same page cross. We study the problem of determining whether $G$ admits a $k$-page book embedding both when the linear order of the vertices is fixed, called ${\rm F{\small IXED}-O{\small RDER}~B{\small OOK}~T{\small HICKNESS}}$, or not fixed, called ${\rm B{\small OOK}~T{\small HICKNESS}}$. Both problems are known to be ${\sf NP}$-complete in general. We show that ${\rm F{\small IXED}-O{\small RDER}~B{\small OOK}~T{\small HICKNESS}}$ and ${\rm B{\small OOK}~T{\small HICKNESS}}$ are fixed-parameter tractable parameterized by the vertex cover number of the graph and that ${\rm F{\small IXED}-O{\small RDER}~B{\small OOK}~T{\small HICKNESS}}$ is fixed-parameter tractable parameterized by the pathwidth of the vertex order.
Zitieren
APA
Bhore, S., Ganian, R., Montecchiani, F., & Nöllenburg, M. (2020). Parameterized Algorithms for Book Embedding Problems. Journal of Graph Algorithms and Applications, 24(4), 603-620. https://doi.org/10.7155/jgaa.00526
Vancouver
Bhore S, Ganian R, Montecchiani F, Nöllenburg M. Parameterized Algorithms for Book Embedding Problems. Journal of Graph Algorithms and Applications. 2020;24(4):603-620. doi:10.7155/jgaa.00526
BibTeX
@article{Bhore2020,
author = {Bhore, Sujoy and Ganian, Robert and Montecchiani, Fabrizio and Nöllenburg, Martin},
title = {Parameterized Algorithms for Book Embedding Problems},
journal = {Journal of Graph Algorithms and Applications},
year = {2020},
volume = {24},
number = {4},
pages = {603--620},
doi = {10.7155/jgaa.00526}
}
EUVIMED