Other formats:
BibTeX
LaTeX
RIS
@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.
|