N-separators in planar graphs

作者：Tishchenko S A^*

来源：European Journal of Combinatorics, 2012, 33(3): 397-407.

DOI：10.1016/j.ejc.2011.09.003

We analyse N-separators in planar weighted graphs for any integer N. The well-known result due to Lipton and Tarjan [5] is obtained in the case N = 2. The existence of an N-separator is examined and the exact bounds for the best separation are demonstrated.

• 出版日期2012-4