problem przy obliczanu planarnosci grafu

[firestorm]

Witam,

Próbuje się nauczyć obliczania planarnosci grafu.
Znam warunek konieczny planarności i wiem że nie jest on wystarczający do jej stwierdzenia.

I tu zaczyna się problem - nie rozumiem o co chodzi
z grafem homeomorficznym.

Tzn czy ten dodatkowy wierzchołek mogę wrzucić na dowolnej krawędzi?
W notakach mam coś o wstawianiu dodatkowej krawędzi pomiędzy "podstawowymi weirzchołkami"...
i już w ogóle się pogubiłem.

Czy mógłby ktoś na podstawie jakiegoś prostego grafu mi to wyjaśnić?

Z góry dzięki!

[kropka+]

Na dowolnej krawędzi zaznaczasz dodatkowy wierzchołek i ten wierzchołek, dzieli starą krawędź na dwie części. Stąd masz w nowym grafie o jedną krawędź więcej.