I am reading this recent paper by Schrijver, in particular, section 4.2: Enumerating homologies of disjoint paths.

I did not understand how do they re-route the paths through a spanning tree and obtain the walks with the mentioned properties, so I decided to work out an example. This is what I have:

enter image description here

A planar graph with two pairs of terminals and want to find vertex disjoint paths between them (that is $F=\{\{1,2\}\}$). I have also marked a spanning tree $T$ (purple highlighted edges) and numbered the edges $e_1, e_2, e_3, e_4$ not in the tree such that if $Q_{e_j}$ is longer than $Q_{e_i}$ then $j > i$. (I haven't marked the direction of the edges because we are considering undirected walks)

enter image description here

Now I have marked two disjoint paths between the terminals. And according to the algorithm next I am supposed to eliminate $e_2$ from $P_2$ and then $e_4$ from $P_1$.

enter image description here

But notice that the two walks now cross each other at the top-middle vertex, but the algorithm claimed that the walks obtained will be non-crossing.

Can someone please point out my mistake. Any help would be really appreciated.

Even in this 1994 paper, they described a way to enumerate homologies but this method, as it is described, seems more difficult for me to understand.

Edit: Following is the only way, I was able to find, to re-route those paths through the tree, but as far as I understand, this is not what the paper describes.

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.