Прямолинейные графы. 
Геометрическая теория графов

Плоский элементарный граф называется прямолинейным графом, если все его ребра являются прямолинейными отрезками. Ясно, что элементарный плоский граф, содержащий не более трех вершин, допускает геометрическую реализацию в виде прямолинейного графа. Известно также, что любая плоская триангуляция допускает геометрическую реализацию в виде прямолинейного графа (доказательство проводится методом математической индукции по количеству вершин; см. [2]). Отсюда, а также из того, что любой элементарный плоский граф является суграфом некоторой плоской триангуляции с тем же количеством вершин (см. теорему 13), следует, что любой элементарный плоский граф изоморфен прямолинейному графу. Этот интересный факт известен в теории графов как теорема Фари.

На практике реализация плоских графов в виде прямолинейных графов является достаточно интересным упражнением. В частности, представляют интерес прямолинейные реализации графов, соответствующие различным простым многогранникам. Так на рис. 52−56.

представлены прямолинейные графы пяти правильных Пример (рис. 69).

многогранников — Платоновых графов,.

Рис. 103.

прямолинейной реализации графакубооктаэдра дает рис. 73. Двойственным многогранником для

кубооктаэдра является ромбический додекаэдр (рис. 67). Прямолинейная реализация графа ромбического додекаэдра представлена на рис. 103.