3
$\begingroup$

I was reading this paper by A. Schrijver on "Finding k disjoint paths in directed planar graphs".

First they describe what are cohomologous functions on a graph. My interpretation of this definition is as follows: Suppose you have a function $\phi: A \rightarrow G$, then you can extend this function to a group homomorphism $\widetilde{\phi}: \pi_1(D, r) \rightarrow G$ as: $$l = (r \xrightarrow{a_1} v_1 \xrightarrow{a_2} v_2 \rightarrow \cdots \xrightarrow{a_{n-1}} v_{n-1} \xrightarrow{a_n} r) \mapsto \phi(a_1)\phi(a_2) \ldots \phi(a_n)$$

Now cohomologous functions just identifies all these homomorphisms, that is $\phi, \psi$ are cohomologous iff $\widetilde{\phi} = \widetilde{\psi}$.

Next they define homologous functions on a graph. I think two functions are homologous if for any vertex on the boundary of outer face, the net flow passing through it remains the same for both the functions.

(The net flow passing through a vertex is defined as $\phi(a_1)^{\epsilon_1}\phi(a_2)^{\epsilon_2} \cdots \phi(a_n)^{\epsilon_n}$ in the clockwise order)

This can be seen by considering the dual graph and then observing that two functions are homologous on a planar graph iff they are cohmologous on the dual graph, as mentioned in the paper, and that any loop at $r$ corresponds to net flow at a corresponding boundary vertex (as I have tried to demonstrate in the picture below).

  • I am not sure if my interpretation for this homologous functions is correct.

  • The author mentions in the beginning of the paper that, this tool gives us a convenient way to "record shift of curves over the plane". I don't see how that follows.

  • Why is the outer face special for this algorithm? Couldn't we have fixed any face $F$ to begin with and consider functions with $f(F)=1$, as opposed to $f(R)=1$?

Any help would be really appreciated.


enter image description here

$\endgroup$
  • $\begingroup$ Not a complete answer, but in our recent paper sites.cs.ucsb.edu/~daniello/papers/… we discuss this (see section 2 on homology and discrete homotopy. This is not a perfect 1-1 correspondence but it might help you get some intuition on what is going on) $\endgroup$ – daniello Jun 12 at 6:11
  • $\begingroup$ @daniello So as you describe discrete homotopy via face move/pull/push operations, the idea behind it is very clear. But I don't get a similar underlying geometric idea for homologous functions. I saw an example using which I can see this homologous operation can transform path via faces but in general what is the topological idea? Why exactly do we call them homologous? $\endgroup$ – kishlaya Jun 13 at 13:33

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.