Separators vs separation
Most versions I've seen of the planar separator theorem give the primary role to the separator and the vertices: a separator is a small set of vertices the removal of which splits the remaining vertices into two subsets of roughly equal size. But when one states it in this way, one actually ends up with three parts (the separator vertices themselves form the third part). How the removal splits the remaining vertices is somewhat unclear, because it's not just into connected components: one may get more than two connected components and then have to regroup them to form the two sides of the split. And there's some ambiguity about where the edges go: all edges incident to the separator are deleted? We group the edges into five different sets according to which one or two vertex subsets they touch?
I think it makes things simpler to put the edges and the split first: a separation is a partition of the edges of the graph into subgraphs. Once you have that part clear, the separator is easy to find: it's just the set of vertices that appear in more than one subgraph of the separation. So the planar separator theorem, rephrased in this way, states that the edges of any planar graph can be partitioned into two subgraphs, with each subgraph having at least \( n/3 \) vertices and with \( O(\sqrt{n}) \) shared vertices.
(Why "at least \( n/3 \)" rather than "at most \( 2n/3 \)"? Because it matches more closely the "at most \( 2n/3 \)" in the usual statement of the separator theorem in which the separator vertices are not counted towards either side. And because it's not true otherwise unless you change it to \( 2n/3 + O(\sqrt{n}) \) or make things messier by adding "for all sufficiently large \( n \)". Consider \( K_4 \): its edges have no partition into two subgraphs with fewer than four vertices in the larger one.)
It's not a big deal; I don't think it makes a difference in terms of correctness or usefulness in any application, but it makes the notation a little cleaner in some cases. The literature on separator theorems is big, and I'm certainly not familiar with it all, so likely this point has been made already several times in several papers. I'd be interested to find out which ones they are.
Comments:
2010-05-18T05:58:59Z
The separation approach is taken by Robertson and Seymour and later by Alon, Seymour and Thomas. I agree that it is much more precise.
- David Wood
2010-05-18T06:09:11Z
Thanks for the references.
2010-05-18T06:11:44Z
Some references that use "separation".
Robertson, N. and Seymour, P. D. 1995. Graph minors. XIII. The disjoint paths problem. J. Combin. Theory Ser. B 63, 1, 65–110.
Alon, N., Seymour, P., and Thomas, R. 1994. Planar separators. SIAM J. Discrete Math. 7, 2, 184–193.
Alon, N., Seymour, P. D., and Thomas, R. 1990b. A separator theorem for nonplanar graphs. J. Amer. Math. Soc. 3, 4, 801–808.
Reed B. and Wood. D. R., A linear time algorithm to find a separator in a graph excluding a minor, ACM Transactions on Algorithms, to appear eventually.
Finally, if you don't care about algorithmic efficiency and leading constants, then I think that the Alon-Seymour-Thomas proof is by far the nicest proof of the planar separator theorem.
2010-05-18T06:19:34Z
I knew about the Alon–Seymour–Thomas minor separator paper (and the Reed–Wood followup that speeds it up at the expense of separator size) but didn't realize they also had one on planar separators; I'll have to take a more careful look at that one.
Usually I do care about algorithmic efficiency, but not this time. I still like the Miller–Teng–Thurston–Vavasis proof, though, maybe because it incorporates more geometry.
2010-05-18T06:40:31Z
I need something like this. AND A BRAIN TO GO WITH IT
2010-05-18T15:50:34Z
On a similar note branch width is closer to separations while tree width is closer to separators. Depending on the application, one or the other is preferred. Branch width generalizes to matroids in a natural fashion while tree width does not.
2010-05-18T16:59:01Z
Hmm...the Wikipedia article on branchwidth is in almost as sad shape as the one on the planar separator theorem. Lots more work left to do there.