Любой чертеж плоскости разделяет плоскость на отдельные области, ограниченные ребрами графа, называемыми гранями. В качестве простого примера, любое вложение треугольника в плоскость разделяет его на две грани: область внутри треугольника и (неограниченную) область вне треугольника. Неограниченная область вне вложения графа называется внешней гранью. Каждое вложение дает одну внешнюю грань и ноль или более внутренних граней. Известный результат, называемый формулой Эйлера, гласит, что для любого плоского графа с n вершинами, e ребрами, f гранями и c связными компонентами
n + f = e + c + 1
Эта формула подразумевает, что у любого плоского графа без петель или параллельных ребер не более 3n - 6 ребер и 2n - 4 граней. Из-за этих границ алгоритмы на плоских графах могут выполняться во времени O (n) или в пространстве O (n) на графе вершин n, даже если им приходится пересекать все ребра или грани графа.
Удобный способ отделить фактический тест на плоскостность от алгоритмов, которые принимают планарный граф в качестве входных данных, через промежуточную структуру, называемую плоским вложением. Вместо того, чтобы указывать абсолютные позиции вершин и ребер в плоскости, как это делает чертеж плоскости, плоское встраивание определяет их положения относительно друг друга. Плоское вложение состоит из последовательности для каждой вершины графа всех ребер, падающих на эту вершину в том порядке, в котором они должны быть нарисованы вокруг этой вершины. Порядки, определенные этой последовательностью, могут представлять итерацию по часовой стрелке или против часовой стрелки через соседей каждой вершины, но ориентация должна быть согласованной по всему встраиванию.
В библиотеке графов надстроек плоское вложение является моделью концепции PlanarEmbedding. Тип, который моделирует PlanarEmbedding, может быть передан в тест на плоскостность и заполнен, если входной граф является плоским. Все остальные алгоритмы планарного графа "back end" принимают это заполненное PlanarEmbedding в качестве входных данных. «