Parameterized Algorithms for Book Embedding Problems

D 2019

Parameterized Algorithms for Book Embedding Problems

BHORE, Sujoy, Robert GANIAN, Fabrizio MONTECCHIANI a Martin NOLLENBURG

Základní údaje

Originální název

Parameterized Algorithms for Book Embedding Problems

Autoři

BHORE, Sujoy (356 Indie), Robert GANIAN (203 Česká republika, garant, domácí), Fabrizio MONTECCHIANI (380 Itálie) a Martin NOLLENBURG (276 Německo)

Vydání

USA, Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, od s. 365-378, 14 s. 2019

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Odkazy

URL

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/19:00113724

Organizační jednotka

Fakulta informatiky

ISBN

978-3-030-35801-3

ISSN

DOI

http://dx.doi.org/10.1007/978-3-030-35802-0_28

UT WoS

000612918800028

Klíčová slova anglicky

Parameterized Complexity

Štítky

core_A, firank_A

Změněno: 16. 5. 2022 14:31, Mgr. Michal Petr

Anotace

V originále

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 Fixed-Order Book Thickness, or not fixed, called Book Thickness. Both problems are known to be NP -complete in general. We show that Fixed-Order Book Thickness and Book Thickness are fixed-parameter tractable parameterized by the vertex cover number of the graph and that Fixed-Order Book Thickness is fixed-parameter tractable parameterized by the pathwidth of the vertex order.

Citovat

BHORE, Sujoy, Robert GANIAN, Fabrizio MONTECCHIANI a Martin NOLLENBURG. Parameterized Algorithms for Book Embedding Problems. Online. In Daniel Archambault, Csaba D. Toth. Graph Drawing and Network Visualization - 27th International Symposium, GD 2019. USA: Springer, 2019, s. 365-378. ISBN 978-3-030-35801-3. Dostupné z: https://dx.doi.org/10.1007/978-3-030-35802-0_28.

@inproceedings{1648261,
   author = {Bhore, Sujoy and Ganian, Robert and Montecchiani, Fabrizio and Nollenburg, Martin},
   address = {USA},
   booktitle = {Graph Drawing and Network Visualization - 27th International Symposium, GD 2019},
   doi = {http://dx.doi.org/10.1007/978-3-030-35802-0_28},
   editor = {Daniel Archambault, Csaba D. Toth},
   keywords = {Parameterized Complexity},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {USA},
   isbn = {978-3-030-35801-3},
   pages = {365-378},
   publisher = {Springer},
   title = {Parameterized Algorithms for Book Embedding Problems},
   url = {https://link.springer.com/chapter/10.1007%2F978-3-030-35802-0_28},
   year = {2019}
}

TY  - JOUR
ID  - 1648261
AU  - Bhore, Sujoy - Ganian, Robert - Montecchiani, Fabrizio - Nollenburg, Martin
PY  - 2019
TI  - Parameterized Algorithms for Book Embedding Problems
PB  - Springer
CY  - USA
SN  - 9783030358013
KW  - Parameterized Complexity
UR  - https://link.springer.com/chapter/10.1007%2F978-3-030-35802-0_28
L2  - https://link.springer.com/chapter/10.1007%2F978-3-030-35802-0_28
N2  - 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 Fixed-Order Book Thickness, or not fixed, called Book Thickness. Both problems are known to be NP -complete in general. We show that Fixed-Order Book Thickness and Book Thickness are fixed-parameter tractable parameterized by the vertex cover number of the graph and that Fixed-Order Book Thickness is fixed-parameter tractable parameterized by the pathwidth of the vertex order.
ER  -

BHORE, Sujoy, Robert GANIAN, Fabrizio MONTECCHIANI a Martin NOLLENBURG. Parameterized Algorithms for Book Embedding Problems. Online. In Daniel Archambault, Csaba D. Toth. \textit{Graph Drawing and Network Visualization - 27th International Symposium, GD 2019}. USA: Springer, 2019, s.~365-378. ISBN~978-3-030-35801-3. Dostupné z: https://dx.doi.org/10.1007/978-3-030-35802-0\_{}28.

Podrobný výpis o publikaci