Изменения

Если <tex>vw </tex> не в разделяющем треугольнике <tex>p & </tex> и <tex>q </tex> – любые общие соседи <tex>v </tex> и <tex>w</tex>. Пусть <tex>(vp, vw, vq, vx_1, vx_2 … ... vx_k) & </tex> и <tex>(wq, wv, wp, wy_1, wy_2 … wy_l... wy_m) </tex> – обход по часовой стрелке ребер, исходящих соостветсвенно из <tex>v </tex> и <tex>w</tex>.Пусть <tex>G' </tex> – планарная триангуляция, полученная из G стягиванием ребра <tex>vw </tex> в вершину <tex>s</tex>. Заменим пары параллельных ребер <tex>vq & </tex> и <tex>wq </tex> на <tex>sq </tex> и <tex>vp & , wp </tex> на <tex>sp</tex>. Получим вершину <tex>s</tex>, из которой исходят ребра <tex>(sp, sy_1, sy_2 … sy_l... sy_m, sq, sx_1, sx_2 … ... sx_k) – </tex> {{---}} по часовой стрелке.

Мы получили граф <tex>G'</tex>, с меньшим числом вершин = равно <tex>V - 1 — </tex> {{---}} то есть его можно уложить на плоскости требуемым образом: все ребра прямые (и сохранен обход по часовой стрелке ребер инцидентных <tex>s</tex>).Для любого E<tex>\varepsilon >0 </tex> обозначим C_E<tex>C_{\varepsilon}(s) </tex> — круг радиуса E<tex>\varepsilon</tex>, с вершиной <tex>s </tex> в центре. Для каждого соседа <tex>t </tex> вершины <tex>s </tex> в графе <tex>G' </tex> обозначим R_E<tex>R_{\varepsilon}(t) </tex> область, содержащую множество всех окрытых отрезков от <tex>t </tex> до каждой точки из C_E<tex>C_{\varepsilon}(s)</tex>.

Возьмем E <tex>\varepsilon</tex> равным минимуму из всех расстояний от вершины <tex>s </tex> до инцидентных ей вершин и до отрезков, проходящих мимо нее.

Тогда получим, что все соседи <tex>t </tex> вершины <tex>s </tex> находятся снаружи C_E<tex>C_{\varepsilon}(s) </tex> и только ребра <tex>G'</tex>, пересекающие R_E<tex>R_{\varepsilon}(t)</tex>, являются инцидентными <tex>s</tex>.

Проведем линию <tex>L </tex> через вершину <tex>s </tex> так, чтобы вершина <tex>p лежла </tex> лежала с одной ее стороны, а <tex>q </tex> — с другой (иначе <tex>L </tex> наложится на ребра <tex>sp & </tex> и <tex>sq. </tex>), и L никакое из ребер <tex>\{sx_i : 1<i<k\} </tex> и <tex>\{sy_i : 1<i<lm\} </tex> не лежало на ней<tex>L</tex>. Ребра <tex>sq & </tex> и <tex>sq </tex> разбивают C_E<tex>C_{\varepsilon}(s) </tex> на две дуги: первая пересекает ребра <tex>\{sx_i : 1<i<k\}</tex>, а вторая — {{---}} ребра <tex>\{sy_i : 1<i<lm\}</tex>. <tex>L </tex> пересекает C_E<tex>C_{\varepsilon}(s) </tex> в двух точках. Расположим <tex>v & </tex> и <tex>w </tex> в этих точках: <tex>v </tex> на дуге, пересекающей <tex>\{sx_i : 1<i<k\}</tex>, а <tex>w </tex> с другой стороны.

Удалим <tex>s </tex> и инцидентные ей ребра, нарисуем прямые ребра <tex>G</tex>, инцидентные <tex>v </tex> и <tex>w</tex>.

Получим, что <tex>vw </tex> лежит на <tex>L</tex>. Так как <tex>p </tex> и <tex>q </tex> лежат с разных сторон <tex>L</tex>, ребра, инцидентные <tex>v </tex> и <tex>w</tex>, не пересекаются. По выбору E<tex>\varepsilon</tex>, ребра, инцидентные <tex>v </tex> и <tex>w</tex>, не пересекают и другие ребра <tex>G</tex>. Таким образом желаемая укладка графа <tex>G </tex> достигнута.