Thanks for reading, let me provide the definitions first.

  1. A separator of a graph $G$ is a set of vertices $C$ such that removing $C$ cuts the graph into two disconnected parts $A, B$ such that they are "roughly even size", namely, $|A|, |B|\le 2|G|/3$.

  2. A graph has separation profile $f(n)$ if any subgraph of size $\le n$ has a separator of size $\le f(n)$.

  3. A $(r, s)$ division of a graph is a division of a graph into regions and boundaries such that each region is of size at most r, and each region has at most s boundary vertices.

So my question is, how can one find a $(r, O(f(r)))$ division of a graph with separation profile $f(n)$? The strategy is, of course: repeatedly finding separators until you arrive at such a division. I know the work of Frederickson's: Fast Algorithms for Shortest Paths in Planar Graphs, with Applications, see page 4-6, and another famous paper Faster Shortest-Path Algorithms for Planar Graphs. In the second paper, before Lemma 2.1, they simply said: a simple adaptation of Frederickson's algorithm will suffice.

My confusion is exactly with this 'simple' adaptation. When you repeatedly find separators, you arrive at a bunch regions of size $\le r$. How can you continue to divide them into ones with small boundaries? In Frederickson's, this is done by using the famous Planar Separator Theorem, which says that given a subgraph, one could assign any weight to its vertices and we could find a separator which separates the weights. Using this theorem, we can assign weights to boundaries of a region, and assign no weights to the region itself, to find a small separator that cuts the boundary. Apply this repeatedly to regions with large boundaries, we are done. See page 6 of the first paper.

I don't yet see how to do this in graphs with separation profiles, precisely because I don't yet see how to cut regions with large boundaries into ones with small boundaries (in a way that the number of smaller regions is bounded). The r-division technique seems to be widely applied in graph algorithms, and I found some papers that will just state that there is a r-division in a separable graph without citation. I'm assuming I'm missing something simple here, and any help would be greatly appreciated. Thank you so much in advance!



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.