학술논문
Parameterized Algorithms for Book Embedding Problems
Document Type
Chapter
Author
Goos, Gerhard, Founding Editor; Hartmanis, Juris, Founding Editor; Bertino, Elisa, Editorial Board Member; Gao, Wen, Editorial Board Member; Steffen, Bernhard, Editorial Board Member; Woeginger, Gerhard, Editorial Board Member; Yung, Moti, Editorial Board Member; Archambault, Daniel, Editor; Tóth, Csaba D., Editor; Bhore, Sujoy; Ganian, Robert; Montecchiani, Fabrizio; Nöllenburg, Martin
Source
Graph Drawing and Network Visualization : 27th International Symposium, GD 2019, Prague, Czech Republic, September 17–20, 2019, Proceedings. 11/28/2019. 11904:365-378
Subject
Language
English
ISSN
0302-9743
1611-3349
1611-3349
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 $$\mathsf {NP}$$ 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.