# How can one find a r-division of a graph with strongly sublinear separation profile (separable graphs)?

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!