Fast algorithm finds disjoint paths in graphs on complex surfaces
Linear-Time FPT Algorithm for Surface Disjoint Paths via Surface Cutting
Data Structures and AlgorithmsComputational Geometry
Summary
Finding multiple routes that don’t cross each other on a map-like structure can be very tricky, especially when the map is drawn on complicated surfaces like a donut shape. The authors developed a new method that quickly solves this problem for maps drawn on surfaces with a certain complexity measure called Euler genus. They break the complex surface into simpler flat parts and use clever techniques to stitch paths together without overlaps. Their work extends previous solutions from flat surfaces to more complex ones.
What this means in practice
- •For network designers: Design communication routes on complex network topologies embedded on surfaces to ensure data paths do not interfere with each other.
- •For circuit layout engineers: Optimize wire routing on multilayer circuit boards modeled as graphs on complex surfaces to avoid signal crossing and interference.
Authors
Kyungjin Cho, Eunjin Oh, Sebastian Wiederrecht
Abstract
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 surface of Euler genus $g$, we present a $2^{O(k^2+g^2)}n$-time algorithm that computes $k$ pairwise vertex-disjoint paths connecting the given vertex pairs if such paths exist. Our approach relies on the decomposition of $G$ into $O(k+g)$ planar subgraphs while bounding the complexity of the boundaries between these subgraphs. This approach enables the use of techniques for compressing linkages in planar graphs. Moreover, our techniques yield two kernels of size polynomial in $k$, $g$, and the treewidth of the graph, and of size $2^{O(k+g)}$. These results extend recent advances on \textsc{$k$-Disjoint Paths} on planar graphs [Cho et al. SODA 2023] and [Włodarczyk and Zehavi FOCS 2023] to surface-embedded graphs.