Укладка графа на плоскости

Определение:

Граф обладает укладкой в пространстве [math]L[/math], если он изоморфен графу, вершинами которого являются некоторые точки пространства, а ребрами — жордановы кривые, соединяющие соответствующие вершины, причем 1) кривая, являющаяся ребром не проходит через другие вершины графа, кроме вершин, которые она соединяет; 2) две кривые, являющиеся ребрами, пересекаются лишь в вершинах, инцидентных одновременно обоим этим ребрам. Соответствующий граф, составленный из точек пространства и жордановых кривых из [math]L[/math], называют укладкой исходного графа.

Определение:

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

Определение:

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

Литература

• Асанов М,, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы