×

\(N\)-separators in planar graphs. (English) Zbl 1230.05115

Summary: We analyse \(N\)-separators in planar weighted graphs for any integer \(N\). The well-known result due to R. J. Lipton and R. E. Tarjan [SIAM J. Appl. Math. 36, 177–189 (1979; Zbl 0432.05022)] 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.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C22 Signed and weighted graphs

Citations:

Zbl 0432.05022
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chiba, N.; Nishizeki, T.; Saito, N., Applications of the Lipton and Tarjan planar separator theorem, J. Inform. Process, 4, 4, 203-207 (1981) · Zbl 0477.68069
[2] Chung, F. R.K.; Graham, R. L., A survey of separator theorems, (Korte, B.; etal., Paths, Flows, and VLSI Layouts (1990), Springer), 17-34
[3] Comellas, F.; Gomez, J., New large graphs with given degree and diameter, (Alavi, Y.; Schwenk, A., Graph Theory, Combinatorics and Algorithms, vol. 1 (1995), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. New York), 221-233 · Zbl 0843.05033
[4] Fellows, M.; Hell, P.; Seyffarth, K., Large planar graphs with given diameter and maximum degree, Discrete Appl. Math., 61, 133-153 (1995) · Zbl 0832.05060
[5] Lipton, R. J.; Tarjan, R. E., A separator theorem for planar graphs, SIAM J. Appl. Math., 36, 2, 177-189 (1979) · Zbl 0432.05022
[6] Rosenberg, A. L.; Heath, L. S., Graph Separators, with Applications (2000), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, Massachusetts, 264 p. · Zbl 0981.68119
[7] W.D. Smith, N.C. Wormald, Geometric separator theorems and applications, in: 39th Annual Symposium on Foundations of Computer Science—FOCS’98, 1998, pp. 232-243.; W.D. Smith, N.C. Wormald, Geometric separator theorems and applications, in: 39th Annual Symposium on Foundations of Computer Science—FOCS’98, 1998, pp. 232-243.
[8] Tishchenko, S. A., Separators in planar graphs as a new characterization tool, Fund. Appl. Math., 8, 1193-1214 (2002) · Zbl 1020.05025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.