|
Fundamentalnaya i Prikladnaya Matematika, 2002, Volume 8, Issue 4, Pages 1193–1214
(Mi fpm706)
|
|
|
|
Separators in planar graphs as a new characterization tool
S. A. Tishchenko School 2
Abstract:
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.
Received: 01.06.2001
Citation:
S. A. Tishchenko, “Separators in planar graphs as a new characterization tool”, Fundam. Prikl. Mat., 8:4 (2002), 1193–1214
Linking options:
https://www.mathnet.ru/eng/fpm706 https://www.mathnet.ru/eng/fpm/v8/i4/p1193
|
Statistics & downloads: |
Abstract page: | 423 | Full-text PDF : | 223 | References: | 49 | First page: | 1 |
|