EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Parameterized Algorithms for Book Embedding Problems

Sujoy Bhore, Robert Ganian, Fabrizio Montecchiani, Martin Nöllenburg

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

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →