1
$\begingroup$

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!

$\endgroup$

0

Your Answer

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