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.
Other formats:   BibTeX LaTeX RIS
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
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher United States of America
Confidentiality degree is not subject to a state or trade secret
Publication form electronic version available online
WWW 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 0302-9743
Doi http://dx.doi.org/10.1007/978-3-030-35802-0_28
UT WoS 000612918800028
Keywords in English Parameterized Complexity
Tags core_A, firank_A
Changed by Changed by: Mgr. Michal Petr, učo 65024. Changed: 16/5/2022 14:31.
Abstract
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.
PrintDisplayed: 25/4/2024 06:08