планарное каноническое упорядочение— это упорядочениеv1, v2, ..., vnвершин максимальногопланарногографа, обладающего свойством, что для каждогоk,3<= k< n, граф, индуцированныйv1, v2, ..., vk
является двусвязным и содержит край{v1, v2}на его внешней стороне.
имеет любые вершины в диапазонеv1, v2, ..., vk, которые примыкают кv(k+1)на его внешней стороне, и эти вершины образуют путь вдоль внешней стороны.
Let Gk be the graph induced by the first k vertices in
the canonical ordering, along with all edges between any of the first k
vertices. After Gk has been drawn, the (k+1)st vertex
can be drawn easily without edge crossings, since it's adjacent only to a
consecutive sequence of vertices on the outer face of Gk.
A planar canonical ordering exists for every maximal planar graph with at
least 2 vertices. planar_canonical_ordering expects the input graph
to have at least 2 vertices.
Планарное каноническое упорядочивание используется в качестве входного сигнала в некоторых алгоритмах построения планарных графов, особенно тех, которые создают прямолинейное встраивание. Де Фрейссейх, Пах и Поллак72впервые доказали существование такого порядка и показали, как вычислить один во времениO(n)на максимальном плоском графике сnвершинами.
Сложность
Если карта индекса вершины обеспечивает постоянный доступ к индексам, эта функция требует времениO(n + m)для плоского графа сnвершинами имкраями. Обратите внимание, что в простом плоском графе сfгранями,mкраями иnвершинами, какf, так иmявляютсяO(n).
