Parameterized Algorithms for Book Embedding Problems

D 2019

Parameterized Algorithms for Book Embedding Problems

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

Basic information

Original name

Parameterized Algorithms for Book Embedding Problems

Authors

BHORE, Sujoy (356 India), Robert GANIAN (203 Czech Republic, guarantor, belonging to the institution), Fabrizio MONTECCHIANI (380 Italy) and Martin NOLLENBURG (276 Germany)

Edition

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

Publisher

Springer

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

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

Publication form

electronic version available online

References:

URL

Impact factor

Impact factor: 0.402 in 2005

RIV identification code

RIV/00216224:14330/19:00113724

Organization unit

Faculty of Informatics

ISBN

978-3-030-35801-3

ISSN

DOI

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

UT WoS

000612918800028

Keywords in English

Parameterized Complexity

Abstract

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 and 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, p. 365-378. ISBN 978-3-030-35801-3. Available from: 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 and 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, p.~365-378. ISBN~978-3-030-35801-3. Available from: https://dx.doi.org/10.1007/978-3-030-35802-0\_{}28.

Detailed Information on Publication Record