Talk:Planar separator theorem
Add topic | This article is rated B-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||
Untitled
[edit]A few thing don't become clear to me from the article: Does the extension of the lemma for values in the open interval (1\2,1) also make use of the breadth-first layering technique? In other words if you would choose a value of 1/2+epsilon instead of 2/3, would the construction of the separator still be a cycle constructed from the breadth-first search tree with some extra edge that is not part of this tree? Also why is 1/2 itself not included in the interval? It seems that Theorem 5 in Djidjev (1982) does have A<=n/2, B<=n/2. 158.143.75.70 (talk) 09:59, 2 August 2014 (UTC)
- From the article: "The constant 2/3 in the statement of the separator theorem is arbitrary and may be replaced by any other number in the open interval (1/2,1) without changing the form of the theorem: a partition into more equal subsets may be obtained from a less-even partition by repeatedly splitting the larger sets in the uneven partition and regrouping the resulting connected components." (boldface added since that part of the sentence is what answers your first question. As for your second question: yes, I think 1/2 without the epsilon can be achieved. —David Eppstein (talk) 04:45, 3 August 2014 (UTC)
Thanks David. This sentence from the article that you quote is, however, not clear to me. It might be easy if you have understood the original papers completely, but just reading the wikipedia article and going through the main text of the originals papers (skipping the technical proofs) I wasn't able to really grasp and find an answer to my first question with certainty. I hope you can clarify further. Thanks! 158.143.189.146 (talk) 12:33, 3 August 2014 (UTC)
- The BFS layering technique will not directly achieve a lower ratio. But by using it multiple times (use once to break into pieces of size at most 2/3, then a second time to the largest piece, etc.) and taking the union of the separators found each time, you can get a separator with a lower ratio but a larger constant in the O-notation for the separator size and and a more complicated separator shape. —David Eppstein (talk) 16:24, 3 August 2014 (UTC)