Combing a Linkage in an Annulus
Petr A. Golovach, Giannos Stamoulis, Dimitrios M. Thilikos · SIAM Journal on Discrete Mathematics · 2023
Abstract. A linkage in a graph [Formula: see text] of size [Formula: see text] is a subgraph [Formula: see text] of [Formula: see text] whose connected components are [Formula: see text] paths. The pattern of a linkage of size [Formula: see text] is the set of [Formula: see text] pairs formed by the endpoints of these paths. A consequence of the Unique Linkage Theorem is the following: there exists a function [Formula: see text] such that if a plane graph [Formula: see text] contains a sequence [Formula: see text] of at least [Formula: see text] nested cycles and a linkage of size at most [Formula: see text] whose pattern vertices lay outside the outer cycle of [Formula: see text] then [Formula: see text] contains a linkage with the same pattern avoiding the inner cycle of [Formula: see text]. In this paper we prove the following variant of this result: Assume that all the cycles in [Formula: see text] are “orthogonally” traversed by a linkage [Formula: see text] and [Formula: see text] is a linkage whose pattern vertices may lay either outside the outer cycle or inside the inner cycle of [Formula: see text]. We prove that there are two functions [Formula: see text], such that if [Formula: see text] has size at most [Formula: see text], [Formula: see text] has size at least [Formula: see text] and [Formula: see text], then there is a linkage with the same pattern as [Formula: see text] that is “internally combed” by [Formula: see text], in the sense that [Formula: see text]. This result applies to any graph that is partially embedded on a disk (where [Formula: see text] is also embedded). In fact, we prove this result in the most general version where the linkage [Formula: see text] is [Formula: see text]-scattered: every two vertices of distinct paths are within a distance bigger than [Formula: see text]. We deduce several variants of this result in the cases where [Formula: see text] and [Formula: see text]. These variants permit the application of the Unique Linkage Theorem on several path routing problems on embedded graphs.