Geodesic
Separators in planar graphs as a~new characterization tool
Fundamentalʹnaâ i prikladnaâ matematika, Tome 8 (2002) no. 4, pp. 1193-1214.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider planar graphs with non-negatively weighted vertices, edges, and faces. We let vertices and edges have nonnegative costs. In the case of triangular graphs with equal weights, the obtained results are proved to be equivalent and optimal. The analysis of planar graphs with non-negatively weighted faces for a given plane embedding enables the separator search in dual graphs. We demonstrate efficient planar graph characterization by the separator method on several classical examples: graphs $K_n$ and $K_{mn}$, graphs of diameter 2. 
@article{FPM_2002_8_4_a16,
     author = {S. A. Tishchenko},
     title = {Separators in planar graphs as a~new characterization tool},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {1193--1214},
     publisher = {mathdoc},
     volume = {8},
     number = {4},
     year = {2002},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2002_8_4_a16/}
}
TY  - JOUR
AU  - S. A. Tishchenko
TI  - Separators in planar graphs as a~new characterization tool
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2002
SP  - 1193
EP  - 1214
VL  - 8
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/FPM_2002_8_4_a16/
LA  - ru
ID  - FPM_2002_8_4_a16
ER  - 
%0 Journal Article
%A S. A. Tishchenko
%T Separators in planar graphs as a~new characterization tool
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2002
%P 1193-1214
%V 8
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/FPM_2002_8_4_a16/
%G ru
%F FPM_2002_8_4_a16
S. A. Tishchenko. Separators in planar graphs as a~new characterization tool. Fundamentalʹnaâ i prikladnaâ matematika, Tome 8 (2002) no. 4, pp. 1193-1214. http://geodesic.mathdoc.fr/item/FPM_2002_8_4_a16/

[1] Aho A. V., Hopcroft J. E., Ulmann J. D., The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974 | Zbl

[2] Lipton R. J., Tarjan R. E., “A separator theorem for planar graphs”, SIAM J. Appl. Math., 36:2 (1979), 177–189 | DOI | MR | Zbl

[3] Smith W. D., Wormald N. C., “Geometric separator theorems and applications”, 39th Annual Symposium on Foundations of Computer Science – FOCS '98, Palo Alto, CA, 1998, 232–243

[4] Alon N., Seymour P., Thomas R., “Planar separators”, SIAM J. Discrete Math., 7:2 (1994), 184–193 | DOI | MR | Zbl

[5] Chung F. R. K., Graham R. L., “A survey of separator theorems”, Paths, Flows, and VLSI Layouts, eds. B. Korte et al., Springer, 1990, 17–34 | MR

[6] Djidjev H. N., “On the problem of partitioning planar graphs”, SIAM J. Alg. Discrete Math., 3:2 (1982), 229–240 | DOI | MR | Zbl

[7] Miller G. L., “Finding small simple cycle separators for $2$-connected planar graphs”, Journal of Computer and System Sciences, 32 (1986), 265–279 | DOI | MR | Zbl

[8] Kirkpatrick D., “Optimal search in planar subdivisions”, SIAM J. Comput., 12 (1983), 28–35 | DOI | MR | Zbl

[9] Chiba N., Nishizeki T., Saito N., “Applications of the Lipton and Tarjan planar separator theorem”, J. Info. Proc., 4:4 (1981), 203–207 | MR

[10] Ravi S. S., Hunt H. B., III, “An application of the planar separator theorem to counting problems”, IPL, 25:5 (1987), 317–322 | DOI | MR

[11] Miller G. L., Teng S.-H., Thurston W., Vavasis S. A., “Geometric separators for finite element meshes”, SIAM J. Sci. Comput., 10:2 (1998), 364–386 | DOI | MR | Zbl

[12] Miller G. L., Teng S.-H., Thurston W., Vavasis S. A., “Separators for sphere-packings and nearest neighbor graphs”, J. ACM, 44:1 (1997), 1–29 | DOI | MR | Zbl

[13] Spielman D. A., Teng S.-H., “Disk packings and planar separators”, 12th Annual ACM Symposium on Computational Geometry, 1996, 349–358

[14] Fellows M., Hell P., Seyffarth K., “Large planar graphs with given diameter and maximum degree”, Discrete Appl. Math., 61 (1995), 133–153 | DOI | MR | Zbl

[15] Lovas L., Plammer M., Prikladnye zadachi teorii grafov, Mir, M., 1998

[16] Kuratowski C., “Sur le problème des courbes gauches en topologie”, Fund. Math., 15 (1930), 271–283 | Zbl

[17] Tischenko S. A., “Maksimalnyi razmer planarnogo grafa ($\Delta=3$, $D=3$)”, Fundam. i prikl. mat., 7:1 (2001), 159–171 | Zbl

[18] Tischenko S. A., “Maksimalnyi razmer grafa diametra $2$ s fiksirovannoi eilerovoi kharakteristikoi”, Fundam. i prikl. mat., 7:4 (2001), 1203–1225 | MR | Zbl

[19] Mitrinovic D. S., Pecaric J. E., Volenec V., Recent advances in geometric inequalities, Kluwer, 1989 | MR

[20] Thomassen C., “Triangulating a surface with a prescribed graph”, JCT B, 57 (1993), 196–206 | MR | Zbl

[21] Hopcroft J. E., Tarjan R. E., “Efficient planarity testing”, J. Assoc. Comput. Math., 21 (1974), 549–568 | MR | Zbl

[22] Dreyfus S. E., Wagner R. A., “The Steiner problem in graphs”, Networks, 1 (1972), 195–207 | DOI | MR | Zbl

[23] Berman P., Ramaiyer V., “Improved approximations for the Steiner tree problem”, J. Algorithms, 17 (1994), 381–408 | DOI | MR | Zbl

[24] Gilbert J. R., Lipton R. J., Tarjan R. E., “A separator theorem for graphs of bounded genus”, J. Algorithms, 5 (1984), 391–407 | DOI | MR | Zbl

[25] Alon N., Seymour P., Thomas R., “A separator theorem for nonplanar graphs”, J. Amer. Math. Soc., 3:4 (1990), 801–808 | DOI | MR | Zbl