12 papers
The Complexity of Undirected Partizan Edge Geography
Yuto Okada
Partizan Edge Geography is a two-player game on a graph where each player has their own token on a vertex and moves their token to a neighbor in a turn removing the edge. Two playe…
Min-1-Planarity is NP-Hard
Yuto Okada
In this paper, we show that it is NP-hard to determine whether a given graph admits a min-1-planar drawing. A drawing of a graph is min--planar if, for every crossing in the dra…
Treewidth of the toroidal grid
Tatsuya Gima, Hiraku Morimoto, Yuto Okada +1
In this paper, we show that the treewidth of the toroidal grid is for all . This closes the gap between the previously known upper bound of (Ell…
One-Sided Local Crossing Minimization
Panos Giannopoulos, Miriam Goetze, Grzegorz Gutowski +6
Drawing graphs with the minimum number of crossings is a classical problem that has been studied extensively. Many restricted versions of the problem have been considered. For exam…
Forcing a unique minimum spanning tree and a unique shortest path
Tatsuya Gima, Andreas Grigorjew, Yasuaki Kobayashi +7
A forcing set in a combinatorial problem is a set of elements such that there is a unique solution that contains all the elements in . An anti-forcing set is the symmetric c…
Hitting Geodesic Intervals in Structurally Restricted Graphs
Tatsuya Gima, Yasuaki Kobayashi, Yuto Okada +2
Given a graph , a set of vertex pairs, and an integer , Hitting Geodesic Intervals asks whether there is a set of size at most such that for e…
2-Layer Fan-Planarity in Polynomial Time
Yasuaki Kobayashi, Yuto Okada
In this paper, we give a polynomial-time algorithm for deciding whether an input bipartite graph admits a 2-layer fan-planar drawing, resolving an open problem posed in several pap…
Pathwidth of 2-Layer -Planar Graphs
Yuto Okada
A bipartite graph is a 2-layer -planar graph if it admits a drawing on the plane such that the vertices in and are placed on two parallel lines respe…
Structural Parameterizations of -Planarity
Tatsuya Gima, Yasuaki Kobayashi, Yuto Okada
The concept of -planarity is extensively studied in the context of Beyond Planarity. A graph is -planar if it admits a drawing in the plane in which each edge is crossed at m…
Recognizing 2-Layer and Outer -Planar Graphs
Yasuaki Kobayashi, Yuto Okada, Alexander Wolff
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-pa…
Basis sequence reconfiguration in the union of matroids
Tesshu Hanaka, Yuni Iwamasa, Yasuaki Kobayashi +2
Given a graph and two spanning trees and in , Spanning Tree Reconfiguration asks whether there is a step-by-step transformation from to such that all inter…
Bounding the Treewidth of Outer -Planar Graphs via Triangulations
Oksana Firman, Grzegorz Gutowski, Myroslav Kryven +2
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 pape…