Planar Canonical Ordering

Computes a canonical ordering of the vertices of a maximal planar graph.

Complexity: O(n + m)
Defined in: <boost/graph/planar_canonical_ordering.hpp>

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boyer_myrvold_planar_test.hpp>
#include <boost/graph/planar_canonical_ordering.hpp>
#include <iostream>
#include <vector>

using namespace boost;

struct Edge { int idx; };

using Graph = adjacency_list<vecS, vecS, undirectedS, no_property, Edge>;
using Vertex = graph_traits<Graph>::vertex_descriptor;
using Descriptor = graph_traits<Graph>::edge_descriptor;

int main() {
    // Start with a triangle (already maximal planar for 3 vertices)
    Graph g(3);
    add_edge(0, 1, g); add_edge(1, 2, g); add_edge(0, 2, g);

    int i = 0;
    for (auto e : make_iterator_range(edges(g))) { g[e].idx = i++; }

    std::vector<std::vector<Descriptor>> storage(num_vertices(g));
    auto embedding = make_iterator_property_map(storage.begin(), get(vertex_index, g));
    boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
        boyer_myrvold_params::embedding = embedding);

    std::vector<Vertex> order;
    planar_canonical_ordering(g, embedding, std::back_inserter(order),
        get(vertex_index, g));

    std::cout << "Planar canonical ordering:";
    for (auto v : order) { std::cout << " " << v; }
    std::cout << "\n";
}

Planar canonical ordering: 0 1 2

Synopsis

template <typename Graph, typename PlanarEmbedding,
          typename OutputIterator, typename VertexIndexMap>
void planar_canonical_ordering(
    const Graph& g,
    PlanarEmbedding embedding,
    OutputIterator ordering,
    VertexIndexMap vm);

Direction Parameter Description

Direction	Parameter	Description
IN	`const Graph& g`	An undirected graph. The type `Graph` must be a model of VertexAndEdgeListGraph. The graph must be maximal planar and have at least two vertices.
IN	`PlanarEmbedding embedding`	A model of PlanarEmbedding.
OUT	`OutputIterator ordering`	An OutputIterator with `value_type` equal to `graph_traits<Graph>::vertex_descriptor`. The canonical ordering will be written to this iterator.
IN	`VertexIndexMap vm`	A Readable Property Map that maps vertices from `g` to distinct integers in the range `[0, num_vertices(g))`. Default: `get(vertex_index, g)`

const Graph& g

An undirected graph. The type Graph must be a model of VertexAndEdgeListGraph. The graph must be maximal planar and have at least two vertices.

PlanarEmbedding embedding

A model of PlanarEmbedding.

OUT

OutputIterator ordering

An OutputIterator with value_type equal to graph_traits<Graph>::vertex_descriptor. The canonical ordering will be written to this iterator.

VertexIndexMap vm

A Readable Property Map that maps vertices from g to distinct integers in the range [0, num_vertices(g)).
Default: get(vertex_index, g)

Description

A planar canonical ordering is an ordering v₁, v₂, …, v_n of the vertices of a maximal planar graph having the property that, for each k, 3 <= k < n, the graph induced by v₁, v₂, …, v_k:

is biconnected and contains the edge {v₁, v₂} on its outer face.
has any vertices in the range v₁, v₂, …, v_k that are adjacent to v_(k+1) on its outer face, and these vertices form a path along the outer face.

Let G_k 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 G_k 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 G_k.

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.

The planar canonical ordering is used as an input in some planar graph drawing algorithms, particularly those that create a straight line embedding. de Fraysseix, Pach, and Pollack [66] first proved the existence of such an ordering and showed how to compute one in time O(n) on a maximal planar graph with n vertices.

Edit this Page