FUNDAMENTALNAYA
I PRIKLADNAYA MATEMATIKA

(FUNDAMENTAL AND APPLIED MATHEMATICS)

2002, VOLUME 8, NUMBER 4, PAGES 1193-1214

**Separators in planar graphs as a new characterization tool**

S. A. Tishchenko

Abstract

View as HTML
View as gif image
View as LaTeX source

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$.

All articles are
published in Russian.

Location: http://mech.math.msu.su/~fpm/eng/k02/k024/k02417h.htm

Last modified: April 10, 2003