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