6
$\begingroup$

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

$\endgroup$

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.