Assume you have a simple and infinite graph. Choose $x_{0}$ an arbitrary vertex and consider $$ G_{n}:=\{x\in G:d(x_0,x)\leq n\} $$ with the graph metric (hop metric). Now for each pair of nodes there is a unit flow that travels through the minimum path between nodes (if there is more than one minimum path it splits equally along all such paths). The total flow in $G_{n}$ is equal to $|G_{n}|^2$.

Given a node $v\in G_{n}$ we define $T_{n}(v)$ as the total flow generated in $G_{n}$ passing through $v$. In other words, $T_{n}(v)$ is the sum off all the geodesic paths in $G_{n}$ which are carrying flow and contain the node $v$. Let $M_{n}$ be the maximum flow $$ M_{n}(v):=\max_{v\in G_{n}}{T_{n}(v)}. $$ For any graph $|G_{n}|\leq M_{n}\leq |G_{n}|^2$. It is not very difficult to see that for $G=\mathbb{Z}^2$ $$ M_{n}=O(|G_{n}|^{3/2}). $$

My question is: can we do better than this in a planar graph? In other words, does there exist a infinite planar graph $G$ such that $M_{n}=o(|G_{n}|^{3/2})$? If so, how low we can go.

Note that the same problem could be reformulated by instead of having an infinite graph $G$ having a sequence of graphs $\{G_{n}\}$ such that $|G_n|\to\infty$.


You can't do better. Lipton and Tarjan's planar separator theorem says that any $n$-node planar graph $G=(V,E)$ contains a set $S$ of $O(\sqrt{n})$ vertices whose removal separates the graph into components all of which have size at most $2n/3$. We can then partition $V \setminus S$ into sets $X,Y$ each containing at least $(1/3-o(1))n$ vertices; there are order $n^2$ pairs $(u,v) \in X \times Y$, and any path between such a pair $(u,v)$ contains a vertex of $S$. Since $|S|=O(\sqrt{n})$, by the pigeonhole principle it follows that some element of $S$ is in order $n^{3/2}$ paths. between $X$ and $Y$.

  • 1
    $\begingroup$ And this works for any flow, not just geodesic. $\endgroup$ – Ori Gurel-Gurevich Feb 20 '12 at 2:33

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.