2026-07-24T12:05:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8566 2024-03-06T10:41:32Z ddc:004 open_access

An Improved Fixed-Parameter Algorithm for One-Page Crossing Minimization Kobayashi, Yasuaki Ohtsuka, Hiromu Tamaki, Hisao Book Embedding Fixed-Parameter Tractability Graph Drawing Treewidth 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yasuaki Kobayashi and Hiromu Ohtsuka and Hisao Tamaki 2018 Is Part Of LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2017.25 urn:nbn:de:0030-drops-85661 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.25 eng https://creativecommons.org/licenses/by/3.0/legalcode