Linear-Time FPT Algorithm for Surface Disjoint Paths via Surface Cutting

Kyungjin Cho, Eunjin Oh, Sebastian Wiederrecht

We study the \textsc{$k$-Disjoint Paths} problem on a graph embedded on a surface with bounded Euler genus. Given a graph $G$ with $n$ vertices and $k$ vertex pairs embedded on a s…