Showing 2026Show all
3 papers · 1 filter
cs.DS2026
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…
cs.CG2026
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…
math.CO2026
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…