Search Results

Documents authored by Okada, Yuto

Document
DOI: 10.4230/LIPIcs.SoCG.2025.65
Recognizing 2-Layer and Outer k-Planar Graphs

Authors: Yasuaki Kobayashi, Yuto Okada, and Alexander Wolff

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
The crossing number of a graph is the least number of crossings over all drawings of the graph in the plane. Computing the crossing number of a given graph is NP-hard, but fixed-parameter tractable (FPT) with respect to the natural parameter. Two well-known variants of the problem are 2-layer crossing minimization and circular crossing minimization, where every vertex must lie on one of two layers, namely two parallel lines, or a circle, respectively. In both cases, edges are drawn as straight-line segments. Both variants are NP-hard, but admit FPT-algorithms with respect to the natural parameter. In recent years, in the context of beyond-planar graphs, a local version of the crossing number has also received considerable attention. A graph is k-planar if it admits a drawing with at most k crossings per edge. In contrast to the crossing number, recognizing k-planar graphs is NP-hard even if k = 1 and hence not likely to be FPT with respect to the natural parameter k. In this paper, we consider the two above variants in the local setting. The k-planar graphs that admit a straight-line drawing with vertices on two layers or on a circle are called 2-layer k-planar and outer k-planar graphs, respectively. We study the parameterized complexity of the two recognition problems with respect to the natural parameter k. For k = 0, the two classes of graphs are exactly the caterpillars and outerplanar graphs, respectively, which can be recognized in linear time. Two groups of researchers independently showed that outer 1-planar graphs can also be recognized in linear time [Hong et al., Algorithmica 2015; Auer et al., Algorithmica 2016]. One group asked explicitly whether outer 2-planar graphs can be recognized in polynomial time. Our main contribution consists of XP-algorithms for recognizing 2-layer k-planar graphs and outer k-planar graphs, which implies that both recognition problems can be solved in polynomial time for every fixed k. We complement these results by showing that recognizing 2-layer k-planar graphs is XNLP-complete and that recognizing outer k-planar graphs is XNLP-hard. This implies that both problems are W[t]-hard for every t and that it is unlikely that they admit FPT-algorithms. On the other hand, we present an FPT-algorithm for recognizing 2-layer k-planar graphs where the order of the vertices on one layer is specified.
Cite as

Yasuaki Kobayashi, Yuto Okada, and Alexander Wolff. Recognizing 2-Layer and Outer k-Planar Graphs. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 65:1-65:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kobayashi_et_al:LIPIcs.SoCG.2025.65,
  author =	{Kobayashi, Yasuaki and Okada, Yuto and Wolff, Alexander},
  title =	{{Recognizing 2-Layer and Outer k-Planar Graphs}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{65:1--65:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.65},
  URN =		{urn:nbn:de:0030-drops-232170},
  doi =		{10.4230/LIPIcs.SoCG.2025.65},
  annote =	{Keywords: 2-layer k-planar graphs, outer k-planar graphs, recognition algorithms, local crossing number, bandwidth, FPT, XNLP, XP, W\lbrackt\rbrack}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.38
Basis Sequence Reconfiguration in the Union of Matroids

Authors: Tesshu Hanaka, Yuni Iwamasa, Yasuaki Kobayashi, Yuto Okada, and Rin Saito

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
Given a graph G and two spanning trees T and T' in G, normalSpanning Tree Reconfiguration asks whether there is a step-by-step transformation from T to T' such that all intermediates are also spanning trees of G, by exchanging an edge in T with an edge outside T at a single step. This problem is naturally related to matroid theory, which shows that there always exists such a transformation for any pair of T and T'. Motivated by this example, we study the problem of transforming a sequence of spanning trees into another sequence of spanning trees. We formulate this problem in the language of matroid theory: Given two sequences of bases of matroids, the goal is to decide whether there is a transformation between these sequences. We design a polynomial-time algorithm for this problem, even if the matroids are given as basis oracles. To complement this algorithmic result, we show that the problem of finding a shortest transformation is NP-hard to approximate within a factor of c log n for some constant c > 0, where n is the total size of the ground sets of the input matroids.
Cite as

Tesshu Hanaka, Yuni Iwamasa, Yasuaki Kobayashi, Yuto Okada, and Rin Saito. Basis Sequence Reconfiguration in the Union of Matroids. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hanaka_et_al:LIPIcs.ISAAC.2024.38,
  author =	{Hanaka, Tesshu and Iwamasa, Yuni and Kobayashi, Yasuaki and Okada, Yuto and Saito, Rin},
  title =	{{Basis Sequence Reconfiguration in the Union of Matroids}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{38:1--38:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.38},
  URN =		{urn:nbn:de:0030-drops-221658},
  doi =		{10.4230/LIPIcs.ISAAC.2024.38},
  annote =	{Keywords: Combinatorial reconfiguration, Matroids, Polynomial-time algorithm, Inapproximability}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.14
Bounding the Treewidth of Outer k-Planar Graphs via Triangulations

Authors: Oksana Firman, Grzegorz Gutowski, Myroslav Kryven, Yuto Okada, and Alexander Wolff

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
The treewidth is a structural parameter that measures the tree-likeness of a graph. Many algorithmic and combinatorial results are expressed in terms of the treewidth. In this paper, we study the treewidth of outer k-planar graphs, that is, graphs that admit a straight-line drawing where all the vertices lie on a circle, and every edge is crossed by at most k other edges. Wood and Telle [New York J. Math., 2007] showed that every outer k-planar graph has treewidth at most 3k + 11 using so-called planar decompositions, and later, Auer et al. [Algorithmica, 2016] proved that the treewidth of outer 1-planar graphs is at most 3, which is tight. In this paper, we improve the general upper bound to 1.5k + 2 and give a tight bound of 4 for k = 2. We also establish a lower bound: we show that, for every even k, there is an outer k-planar graph with treewidth k+2. Our new bound immediately implies a better bound on the cop number, which answers an open question of Durocher et al. [GD 2023] in the affirmative. Our treewidth bound relies on a new and simple triangulation method for outer k-planar graphs that yields few crossings with graph edges per edge of the triangulation. Our method also enables us to obtain a tight upper bound of k + 2 for the separation number of outer k-planar graphs, improving an upper bound of 2k + 3 by Chaplick et al. [GD 2017]. We also consider outer min-k-planar graphs, a generalization of outer k-planar graphs, where we achieve smaller improvements.
Cite as

Oksana Firman, Grzegorz Gutowski, Myroslav Kryven, Yuto Okada, and Alexander Wolff. Bounding the Treewidth of Outer k-Planar Graphs via Triangulations. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{firman_et_al:LIPIcs.GD.2024.14,
  author =	{Firman, Oksana and Gutowski, Grzegorz and Kryven, Myroslav and Okada, Yuto and Wolff, Alexander},
  title =	{{Bounding the Treewidth of Outer k-Planar Graphs via Triangulations}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.14},
  URN =		{urn:nbn:de:0030-drops-212988},
  doi =		{10.4230/LIPIcs.GD.2024.14},
  annote =	{Keywords: treewidth, outerplanar graphs, outer k-planar graphs, outer min-k-planar graphs, cop number, separation number}
}
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact