A weak immersion relation on graphs and its applications Original Research Article

Weak immersion is a generalization of the immersion relation defined by Nash-Williams. A graph H is said to be weakly immersed in a graph G if H can be obtained from G by a sequence of these three operations: taking a subgraph, splitting a vertex, and lifting a pair of adjacent edges. The weak immersion relation has the useful property that finite graphs are well-quasi-ordered by it, which also holds for graphs with some vertices designated as terminals. As a result, any family of finite graphs that is closed under weak immersion can be characterized by a finite number of minimal forbidden graphs called obstructions. Weak immersion offers two advantages over immersion for practical applications. First, although closure under weak immersion implies closure under immersion, families can have significantly fewer obstructions under weak immersion. Hence weak immersion can provide simpler characterizations for closed families. Examples include graphs of bounded cutwidth and graphs of bounded multiway cutsize. The difference in the number of obstructions is at least exponential in the cutwidth and in the square-root of the multiway cutsize. Second, for every fixed graph H, there is a polynomial-time algorithm to decide whether H is weakly immersed in an input graph G. Consequently, there is a polynomial-time membership test for any family that is closed under weak immersion. In principle, testing for weak immersion is as fast as testing for immersion. Thus the simpler characterization provided by weak immersion may lead to faster membership algorithms.