1 Search Results for "Ohtsuka, Hiromu"

Document
DOI: 10.4230/LIPIcs.IPEC.2017.25
An Improved Fixed-Parameter Algorithm for One-Page Crossing Minimization

Authors: Yasuaki Kobayashi, Hiromu Ohtsuka, and Hisao Tamaki

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{kobayashi_et_al:LIPIcs.IPEC.2017.25,
  author =	{Kobayashi, Yasuaki and Ohtsuka, Hiromu and Tamaki, Hisao},
  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 =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.25},
  URN =		{urn:nbn:de:0030-drops-85661},
  doi =		{10.4230/LIPIcs.IPEC.2017.25},
  annote =	{Keywords: Book Embedding, Fixed-Parameter Tractability, Graph Drawing, Treewidth}
}
  • Refine by Author
  • 1 Kobayashi, Yasuaki
  • 1 Ohtsuka, Hiromu
  • 1 Tamaki, Hisao

  • Refine by Classification

  • Refine by Keyword
  • 1 Book Embedding
  • 1 Fixed-Parameter Tractability
  • 1 Graph Drawing
  • 1 Treewidth

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

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 Imprint Privacy Contact