Определение: Граф G изоморфно укладывается на плоскость, если его можно изобразить на плоскости без пересечения ребер, исключая соединения ребер в вершинах. Граф G, уложенный на плоскость, называется плоским изображением графа G. Граф G планарен, если он может быть уложен на плоскость.

Замечание: Всякий плоский граф планарен, всякий подграф планарного графа (плоского) планарен (плосок). Плоский граф иногда называется плоской картой.

Определение: Грань плоского графа есть часть плоскости, ограниченная простым циклом графа. Конечная грань называется внутренней, бесконечная грань называется внешней.

Простой цикл, ограничивающий грань, называется границей грани. Дерево имеет единственную бесконечную внешнюю грань (при отсутствии конечной грани).

Планарн.G

Плоское изображение G

Замечание: Аналогичные Определение можно ввести для мультиграфов и псевдографов. Возможны укладки графов без пересечнеий ребер и на другие поверхности, например: сферу, тор.

Комментарии запрещены.