4 papers
On Edge-Disjoint Maximal Outerplanar Graphs
Yuto Okada, Yota Otachi, Lena Volk
We provide two constructions for edge-disjoint maximal outerplanar graphs on every number of vertices. The bound on the minimum number of vertices is tight. These c…
Finding a Maximum Common (Induced) Subgraph: Structural Parameters Revisited
Tesshu Hanaka, Yuto Okada, Yota Otachi +1
We study the parameterized complexity of the problems of finding a maximum common (induced) subgraph of two given graphs. Since these problems generalize several NP-complete proble…
Dichotomies for Tree Minor Containment with Structural Parameters
Tatsuya Gima, Soh Kumabe, Kazuhiro Kurita +2
The problem of determining whether a graph contains another graph as a minor, referred to as the minor containment problem, is a fundamental problem in the field of graph a…
Sequentially Swapping Tokens: Further on Graph Classes
Hironori Kiya, Yuto Okada, Hirotaka Ono +1
We study the following variant of the 15 puzzle. Given a graph and two token placements on the vertices, we want to find a walk of the minimum length (if any exists) such that the…