Combing a Linkage in an Annulus

Abstract

A linkage in a graph 𝐺 of size 𝑘 is a subgraph 𝐿 of 𝐺 whose connected components are 𝑘 paths. The pattern of a linkage of size 𝑘 is the set of 𝑘 pairs formed by the endpoints of these paths. A consequence of the Unique Linkage Theorem is the following: there exists a function 𝑓:ℕ→ℕ such that if a plane graph 𝐺 contains a sequence C of at least 𝑓⁡(𝑘) nested cycles and a linkage of size at most 𝑘 whose pattern vertices lay outside the outer cycle of C, then 𝐺 contains a linkage with the same pattern avoiding the inner cycle of C. In this paper we prove the following variant of this result: Assume that all the cycles in C are “orthogonally” traversed by a linkage 𝑃 and 𝐿 is a linkage whose pattern vertices may lay either outside the outer cycle or inside the inner cycle of C:=[𝐶1,…,𝐶𝑝,…,𝐶2⁢𝑝−1]. We prove that there are two functions 𝑔,𝑓:ℕ→ℕ, such that if 𝐿 has size at most 𝑘, 𝑃 has size at least 𝑓⁡(𝑘), and |C|≥𝑔⁡(𝑘), then there is a linkage with the same pattern as 𝐿 that is “internally combed” by 𝑃, in the sense that 𝐿∩𝐶𝑝⊆𝑃∩𝐶𝑝. This result applies to any graph that is partially embedded on a disk (where C is also embedded). In fact, we prove this result in the most general version where the linkage 𝐿 is 𝑠-scattered: every two vertices of distinct paths are within a distance bigger than 𝑠. We deduce several variants of this result in the cases where 𝑠=0 and 𝑠>0. These variants permit the application of the Unique Linkage Theorem on several path routing problems on embedded graphs.