Abstract
Book embedding is one of the most wellknown 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 onepage book embedding, which we call onepage crossing minimization. Here, we are given a graph G with n vertices together with a nonnegative 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 fixedparameter tractable. Their algorithm is derived through the application of Courcelle's theorem (on graph properties definable in the monadic secondorder 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 onepage 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 FixedParameter Algorithm for OnePage Crossing Minimization}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {25:125:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770514},
ISSN = {18688969},
year = {2018},
volume = {89},
editor = {Daniel Lokshtanov and Naomi Nishimura},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8566},
URN = {urn:nbn:de:0030drops85661},
doi = {10.4230/LIPIcs.IPEC.2017.25},
annote = {Keywords: Book Embedding, FixedParameter Tractability, Graph Drawing, Treewidth}
}
Keywords: 

Book Embedding, FixedParameter Tractability, Graph Drawing, Treewidth 
Collection: 

12th International Symposium on Parameterized and Exact Computation (IPEC 2017) 
Issue Date: 

2018 
Date of publication: 

02.03.2018 