6 papers · 1 filter
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…
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…
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…