Document Open Access Logo

An Improved Fixed-Parameter Algorithm for One-Page Crossing Minimization

Authors Yasuaki Kobayashi, Hiromu Ohtsuka, Hisao Tamaki

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2017.25.pdf
  • Filesize: 0.51 MB
  • 12 pages

Document Identifiers

Author Details

Yasuaki Kobayashi
Hiromu Ohtsuka
Hisao Tamaki

Cite As Get BibTex

Yasuaki Kobayashi, Hiromu Ohtsuka, and Hisao Tamaki. An Improved Fixed-Parameter Algorithm for One-Page Crossing Minimization. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 25:1-25:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.IPEC.2017.25

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.

Subject Classification

Keywords
  • Book Embedding
  • Fixed-Parameter Tractability
  • Graph Drawing
  • Treewidth

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. M. J. Bannister and D. Eppstein. Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth. In Proc. of GD 2014, pages 210-221. Springer, 2014. Google Scholar
  2. M. Baur and U. Brandes. Crossing reduction in circular layouts. WG, 3353:332-343, 2004. Google Scholar
  3. F. Bernhart and P. C. Kainen. The book thickness of a graph. Journal of Combinatorial Theory, Series B, 27(3):320-331, 1979. Google Scholar
  4. G. Blin, G. Fertin, D. Hermelin, and S. Vialette. Fixed-parameter algorithms for protein similarity search under mRNA structure constraints. Journal of Discrete Algorithms, 6(4):618-626, 2008. Google Scholar
  5. H. L. Bodlaender, P. G. Drange, M. S. Dregi, F. V. Fomin, D. Lokshtanov, and M. Pilipczuk. A c^kn 5-Approximation Algorithm for Treewidth. SIAM Journal on Computing, 45(2):317-378, 2016. Google Scholar
  6. G. Chartrand and F. Harary. Planar Permutation Graphs. Annales de l'I.H.P. Probabilités et statistiques, 3(4):433-438, 1967. Google Scholar
  7. F. R. K. Chung, F. Thomson Leighton, and A. L. Rosenberg. Embedding graphs in books: a layout problem with applications to VLSI design. SIAM Journal on Algebraic Discrete Methods, 8(1):33-58, 1987. Google Scholar
  8. B. Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and computation, 85(1):12-75, 1990. Google Scholar
  9. B. Courcelle and M. Mosbah. Monadic second-order evaluations on tree-decomposable graphs. Theoretical Computer Science, 109(1):49-82, 1993. Google Scholar
  10. V. Dujmović, M. R. Fellows, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, S. Whitesides, and D. R. Wood. On the parameterized complexity of layered graph drawing. Algorithmica, 52(2):267-292, 2008. Google Scholar
  11. M. Frick and M. Grohe. The complexity of first-order and monadic second-order logic revisited. Annals of Pure and Applied Logic, 130(1):3-31, 2004. Google Scholar
  12. R. Fulek, H. He, O. Sỳkora, and I. Vrt'o. Outerplanar crossing numbers of 3-row meshes, Halin graphs and complete p-partite graphs. SOFSEM 2005: Theory and Practice of Computer Science, pages 376-379, 2005. Google Scholar
  13. H. He, A. Sălăgean, and E. Mäkinen. One-and two-page crossing numbers for some types of graphs. International Journal of Computer Mathematics, 87(8):1667-1679, 2010. Google Scholar
  14. J. Hopcroft and R. Tarjan. Algorithm 447: efficient algorithms for graph manipulation. Communications of the ACM, 16(6):372-378, 1973. Google Scholar
  15. P. C. Kainen. The book thickness of a graph II. Congressus Numerantium, 71:121-132, 1990. Google Scholar
  16. T. Kloks. Treewidth: computations and approximations, volume 842. Springer Science &Business Media, 1994. Google Scholar
  17. E. Mäkinen. On circular layouts. International Journal of Computer Mathematics, 24(1):29-37, 1988. Google Scholar
  18. S. Masuda, T. Kashiwabara, K. Nakajima, and T. Fujisawa. On the NP-completeness of a computer network layout problem. In Proceedings of the 1987 IEEE International Symp. on Circuits and Systems, pages 292-295, 1987. Google Scholar
  19. S. L. Mitchell. Linear algorithms to recognize outerplanar and maximal outerplanar graphs. Information Processing Letters, 9(5):229-232, 1979. Google Scholar
  20. F. Shahrokhi, O. Sỳkora, L. A. Székely, and I. Vrt'o. Book embeddings and crossing numbers. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 256-268. Springer, 1994. Google Scholar
  21. J. M. Six and I. G. Tollis. Circular drawings of biconnected graphs. In ALENEX, volume 99, pages 57-73. Springer, 1999. Google Scholar
  22. M. M. Sysło. Characterizations of outerplanar graphs. Discrete Mathematics, 26(1):47-53, 1979. Google Scholar
  23. M. Yannakakis. Embedding planar graphs in four pages. Journal of Computer and System Sciences, 38(1):36-67, 1989. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact