# Asymptotic Geodesic Flow on Planar Graphs

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$.