License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2017.25
URN: urn:nbn:de:0030-drops-85661
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8566/
Kobayashi, Yasuaki ;
Ohtsuka, Hiromu ;
Tamaki, Hisao
An Improved Fixed-Parameter Algorithm for One-Page Crossing Minimization
Abstract
Book embedding is one of the most well-known graph drawing models and is extensively studied in the literature. The special case where the number of pages is one is of particular interest: an embedding in this case has a natural circular representation useful for visualization and graphs that can be embedded in one page without crossings form an important graph class, namely that of outerplanar graphs.
In this paper, we consider the problem of minimizing the number of crossings in a one-page book embedding, which we call one-page crossing minimization. Here, we are given a graph G with n vertices together with a non-negative integer k and are asked whether G can be embedded into a single page with at most k crossings. Bannister and Eppstein (GD 2014) showed that this problem is fixed-parameter tractable. Their algorithm is derived through the application of Courcelle's theorem (on graph properties definable in the monadic second-order logic of graphs) and runs in f(L)n time, where L = 2^{O(k^2)} is the length of the formula defining the property that the one-page crossing number is at most k and f is a computable function without any known upper bound expressible as an elementary function. We give an explicit dynamic programming algorithm with a drastically improved running time of 2^{O(k log k)}n.
BibTeX - Entry
@InProceedings{kobayashi_et_al:LIPIcs:2018:8566,
author = {Yasuaki Kobayashi and Hiromu Ohtsuka and Hisao Tamaki},
title = {{An Improved Fixed-Parameter Algorithm for One-Page Crossing Minimization}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {25:1--25:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Daniel Lokshtanov and Naomi Nishimura},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8566},
URN = {urn:nbn:de:0030-drops-85661},
doi = {10.4230/LIPIcs.IPEC.2017.25},
annote = {Keywords: Book Embedding, Fixed-Parameter Tractability, Graph Drawing, Treewidth}
}
|
Keywords: |
|
Book Embedding, Fixed-Parameter Tractability, Graph Drawing, Treewidth |
|
Collection: |
|
12th International Symposium on Parameterized and Exact Computation (IPEC 2017) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
02.03.2018 |
