<p>I was reading <a href="https://ir.cwi.nl/pub/2257/2257D.pdf" rel="nofollow noreferrer">this</a> paper by A. Schrijver on "Finding k disjoint paths in directed planar graphs".</p>

<p>First they describe what are cohomologous functions on a graph. My interpretation of this definition is as follows: Suppose you have a function <span class="math-container">$\phi: A \rightarrow G$</span>, then you can extend this function to a group homomorphism <span class="math-container">$\widetilde{\phi}: \pi_1(D, r) \rightarrow G$</span> as: 
<span class="math-container">$$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)$$</span> </p>

<p>Now cohomologous functions just identifies all these homomorphisms, that is <span class="math-container">$\phi, \psi$</span> are cohomologous iff <span class="math-container">$\widetilde{\phi} = \widetilde{\psi}$</span>.</p>

<p>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.</p>

<p>(The net flow passing through a vertex is defined as <span class="math-container">$\phi(a_1)^{\epsilon_1}\phi(a_2)^{\epsilon_2} \cdots \phi(a_n)^{\epsilon_n}$</span> in the clockwise order)</p>

<p>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 <span class="math-container">$r$</span> corresponds to net flow at a corresponding boundary vertex (as I have tried to demonstrate in the picture below).</p>

<ul>
<li><p>I am not sure if my interpretation for this homologous functions is correct.</p></li>
<li><p>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.</p></li>
<li><p>Why is the outer face special for this algorithm? Couldn't we have fixed any face <span class="math-container">$F$</span> to begin with and consider functions with <span class="math-container">$f(F)=1$</span>, as opposed to <span class="math-container">$f(R)=1$</span>?</p></li>
</ul>

<p>Any help would be really appreciated. </p>

<hr>

<p><a href="https://i.sstatic.net/FhLIq.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/FhLIq.png" alt="enter image description here"></a></p>

CC BY-SA 4.0
2020-06-12T06:11:12.830Z
Not a complete answer, but in our recent paper https://sites.cs.ucsb.edu/~daniello/papers/planarDisjointPathsSTOC2020.pdf 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)
daniello
CC BY-SA 4.0
2020-06-13T13:33:04.287Z
@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](https://i.sstatic.net/Wm9Ti.png) 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?
kishlaya
<planar-graphs><algebraic-topology><disjoint-paths><homomorphism>
Homologous flows on planar graphs
kishlaya
# Homologous flows on planar graphs

(Asked by: username_0 on 2020-06-11)

I was reading [this](https://ir.cwi.nl/pub/2257/2257D.pdf) 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](https://i.sstatic.net/FhLIq.png)](https://i.sstatic.net/FhLIq.png)

**Tags:** planar-graphs, algebraic-topology, disjoint-paths, homomorphism

> **Comments:**
> **username_1**: Not a complete answer, but in our recent paper https://sites.cs.ucsb.edu/~username_1/papers/planarDisjointPathsSTOC2020.pdf 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)  
> **username_0**: @username_1 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](https://i.sstatic.net/Wm9Ti.png) 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?  

---

## 0 answers

