9 papers
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…
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…
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…
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…