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