5 papers
Fast and Practical Single-Exponential Algorithms for Branchwidth
Taiki Kaneda, Yasuaki Kobayashi, Hisao Tamaki
In this paper, we present exact exponential algorithms for computing branchwidth that are fast both in theory and in practice. The running times of these algorithms are single-expo…
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…
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…
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…