TY - JOUR

T1 - COMBING A LINKAGE IN AN ANNULUS

AU - Golovach, Petr A.

AU - Stamoulis, Giannos

AU - Thilikos, Dimitrios M.

N1 - Publisher Copyright:
© 2023 Society for Industrial and Applied Mathematics Publications. All rights reserved.

PY - 2023

Y1 - 2023

N2 - A linkage in a graph G of size k is a subgraph L of G whose connected components are k paths. The pattern of a linkage of size k is the set of k pairs formed by the endpoints of these paths. A consequence of the Unique Linkage Theorem is the following: there exists a function f : N → N such that if a plane graph G contains a sequence C of at least f(k) nested cycles and a linkage of size at most k whose pattern vertices lay outside the outer cycle of C, then G 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 P and L is a linkage whose pattern vertices may lay either outside the outer cycle or inside the inner cycle of C := [C1, . . ., Cp, . . ., C2p-1]. We prove that there are two functions g, f : N → N, such that if L has size at most k, P has size at least f(k), and |C| ≥ g(k), then there is a linkage with the same pattern as L that is ``internally combed"" by P, in the sense that L ∩ Cp ⊆ P ∩ Cp. 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 L is s-scattered: every two vertices of distinct paths are within a distance bigger than s. We deduce several variants of this result in the cases where s = 0 and s > 0. These variants permit the application of the Unique Linkage Theorem on several path routing problems on embedded graphs.

AB - A linkage in a graph G of size k is a subgraph L of G whose connected components are k paths. The pattern of a linkage of size k is the set of k pairs formed by the endpoints of these paths. A consequence of the Unique Linkage Theorem is the following: there exists a function f : N → N such that if a plane graph G contains a sequence C of at least f(k) nested cycles and a linkage of size at most k whose pattern vertices lay outside the outer cycle of C, then G 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 P and L is a linkage whose pattern vertices may lay either outside the outer cycle or inside the inner cycle of C := [C1, . . ., Cp, . . ., C2p-1]. We prove that there are two functions g, f : N → N, such that if L has size at most k, P has size at least f(k), and |C| ≥ g(k), then there is a linkage with the same pattern as L that is ``internally combed"" by P, in the sense that L ∩ Cp ⊆ P ∩ Cp. 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 L is s-scattered: every two vertices of distinct paths are within a distance bigger than s. We deduce several variants of this result in the cases where s = 0 and s > 0. These variants permit the application of the Unique Linkage Theorem on several path routing problems on embedded graphs.

KW - irrelevant vertex technique

KW - linkage

KW - treewidth

UR - http://www.scopus.com/inward/record.url?scp=85182207636&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85182207636&partnerID=8YFLogxK

U2 - 10.1137/22M150914X

DO - 10.1137/22M150914X

M3 - Article

AN - SCOPUS:85182207636

SN - 0895-4801

VL - 37

SP - 2332

EP - 2364

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 4

ER -