Теорема Фари о распрямлении графа

Не следует путать с теоремой Фарри — утверждением, относящимся к квантовой электродинамике.

Теорема Фа́ри — теоретико-графовое утверждение о возможности выпрямить рёбра любого планарного графа. Иными словами, разрешение рисовать рёбра не в виде отрезков, а в виде кривых, не расширяет класс планарных графов.

Названа в честь венгерского математика Иштвана Фа́ри, хотя была доказана независимо Клаусом Вагнером в 1936 и Штайном в 1951.

Формулировка: любой простой планарный граф имеет плоское представление, в котором все рёбра представлены в виде отрезков прямых.

Доказательство

Шаг индукции.

Один из путей доказательства теоремы Фари — применение математической индукции. Пусть $G$ — простой планарный граф с $n$ вершинами. Мы можем считать граф максимальным планарным, при необходимости можем добавить рёбра в исходный граф $G$. Все грани графа $G$ в этом случае должны быть треугольниками, так как мы можем добавить ребро в любую грань с бо́льшим числом сторон, не нарушая планарности графа, что противоречит соглашению о максимальности графа. Выберем некоторые три вершины $a,b,c$, образующие треугольную грань графа $G$. Мы докажем по индукции по $n$, что существует комбинаторно изоморфное другое вложение с прямыми рёбрами графа $G$, в котором треугольник $abc$ является внешней гранью вложения. (Комбинаторная изоморфность означает, что вершины, рёбра и грани нового рисунка могут быть сделаны соответствующими элементам старого рисунка и при этом сохраняются все отношения инцидентности между рёбрами, вершинами и гранями, не только между вершинами и рёбрами.) База индукции тривиальна, когда $a,b,c$ являются единственными вершинами в $G$ ($n=3$).

По формуле Эйлера для планарных графов граф $G$ имеет $3n-6$ рёбер. Эквивалентно, если определить дефицит вершины $v$ в графе $G$ как $6-\deg(v)$, сумма дефицитов равна 12. Каждая вершина в графе $G$ может иметь дефицит не выше трёх, так что имеется по меньшей мере четыре вершины с положительным дефицитом. В частности, мы можем выбрать вершину $v$ с не более чем пятью соседями, которая отлична от $a,b$ и $c$. Пусть $G'$ образуется путём удаления вершины $v$ из графа $G$ и триангуляции грани $f$, полученной после удаления вершины $v$. По индукции, граф $G'$ имеет комбинаторно изоморфное вложение с прямолинейными рёбрами, в котором $abc$ является внешней гранью. Поскольку полученное вложение $G$ было комбинаторно изоморфно $G'$, удаление из него рёбер, которые были добавлены для получения графа $G'$ оставляет грань $f$, которая теперь представляет собой многоугольник $P$ с не более чем пятью сторонами. Для получения рисунка $G$ с комбинаторно изоморфным вложением с прямыми рёбрами, вершина $v$ должна быть добавлена в многоугольник и соединена отрезками с вершинами многоугольника. По теореме о картинной галерее существует точка внутри $P$, куда можно поместить вершину $v$, так что рёбра, соединяющие вершину $v$ с вершинами многоугольника $P$, не пересекут другие рёбра многоугольника, что завершает доказательство.

Шаг индукции доказательства проиллюстрирован справа.

Связанные результаты

Де Фрейсикс, Пах и Полак показали, как найти за линейное время рисунок с прямолинейными рёбрами на решётке с размерами, линейно зависящими от размера графа, давая универсальное множество точек с квадратичными размерами. Похожий метод использовал Шнайдер для доказательства улучшенных границ и характеристики планарности, где он основывался на частичном порядке инцидентности. Его работа делает упор на существование определённого разбиения рёбер максимального планарного графа на три дерева, которые известны как лес Шнайдера.

Теорема Татта «о резиновой укладке» утверждает, что любой трёхсвязный планарный граф можно нарисовать на плоскости без пересечений так, что его рёбра являются отрезками прямых и внешняя грань является выпуклым многоугольником. Название отражает факт, что такое вложение может быть найдено как точка равновесия системы пружин, представляющих рёбра графа.

Теорема Штайница утверждает, что любой 3-связный планарный граф может быть представлен как рёбра выпуклого многогранника в трёхмерном пространстве. Вложение с прямыми рёбрами графа $G$ может быть получено как проекция такого многогранника на плоскость.

Теорема об упаковке кругов утверждает, что любой планарный граф может быть представлен как граф пересечений набора непересекающихся окружностей на плоскости. Если разместить каждую вершину графа в центре соответствующей окружности, получим представление графа с прямолинейными рёбрами.

Нерешённые проблемы математики: Существует ли для любого планарного графа представление с прямыми рёбрами, в котором длины всех рёбер являются целыми числами?

Хайуо Харборт поднял вопрос, существует ли для любого планарного графа представление с прямыми рёбрами, в котором все длины рёбер являются целыми числами. Верна ли гипотеза Харборта, остаётся открытым вопросом (на 2014 год). Однако известно, что вложение с целочисленными прямыми рёбрами существует для кубических графов.

Сакс поднял вопрос, имеет ли любой граф с незацепленным вложением в трёхмерном евклидовом пространстве незацепленное вложение, в котором все рёбра представлены отрезками по аналогии с теоремой Фари для двухмерных вложений.

См. также

• Минимизация изломов

Литература

• István Fáry. On straight-line representation of planar graphs // Acta Sci. Math. (Szeged). — 1948. — Т. 11. — С. 229–233.
• Gary Chartrand, Linda Lesniak, Ping Zhang. Graphs & Digraphs. — 5th. — CRC Press, 2010. — С. 259–260. — ISBN 9781439826270.
• Hubert de Fraysseix, János Pach, Richard Pollack. Small sets supporting Fary embeddings of planar graphs // Twentieth Annual ACM Symposium on Theory of Computing. — 1988. — С. 426–433. — ISBN 0-89791-264-0. — doi:10.1145/62212.62254.
• Hubert de Fraysseix, János Pach, Richard Pollack. How to draw a planar graph on a grid // Combinatorica. — 1990. — Т. 10. — С. 41–51. — doi:10.1007/BF02122694.
• Jim Geelen, Anjie Guo, David McKinnon. Straight line embeddings of cubic planar graphs with integer edge lengths // J. Graph Theory. — 2008. — Т. 58, вып. 3. — С. 270–274. — doi:10.1002/jgt.20304.
• Harborth H., Kemnitz A., Moller M., Sussenbach A. Ganzzahlige planare Darstellungen der platonischen Korper // Elem. Math.. — 1987. — Т. 42. — С. 118–122.
• Kemnitz A., Harborth H. Plane integral drawings of planar graphs // Discrete Math.. — 2001. — Т. 236. — С. 191–195. — doi:10.1016/S0012-365X(00)00442-8.
• Bojan Mohar, Carsten Thomassen. Graphs on Surfaces. — Johns Hopkins University Press, 2001. — С. roblem 2.8.15. — ISBN 0-8018-6689-8.
• Horst Sachs. Graph Theory: Proceedings of a Conference held in Łagów, Poland, February 10–13, 1981. — Springer-Verlag, 1983. — Т. 1018. — С. 230–241. — ISBN 978-3-540-12687-4. — doi:10.1007/BFb0071633.
• Walter Schnyder. Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA). — 1990. — С. 138–148.
• Stein S. K. Convex maps // Proceedings of the American Mathematical Society. — 1951. — Т. 2, вып. 3. — С. 464–466. — doi:10.2307/2031777. — .
• Tutte W. T. How to draw a graph // Proceedings of the London Mathematical Society. — 1963. — Т. 13. — С. 743–767. — doi:10.1112/plms/s3-13.1.743.
• Klaus Wagner. Bemerkungen zum Vierfarbenproblem // Jahresbericht der Deutschen Mathematiker-Vereinigung. — 1936. — Т. 46. — С. 26–32..