# Planar Canonical Ordering

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

A *planar canonical ordering* is an ordering *v*_{1},
v_{2}, ..., 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*_{1}, v_{2}, ..., v_{k}

- is biconnected and contains the edge
*{v*_{1}, v_{2}}
on its outer face.
- has any vertices in the range
*v*_{1}, v_{2}, ...,
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
[72]
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.

### Complexity

If the vertex index map provides constant-time access to indices, this
function takes time *O(n + m)* for a planar graph with *n* vertices
and *m* edges. Note that
in a simple planar graph with *f* faces, *m* edges, and *n*
vertices, both *f* and *m* are *O(n)*.
### Where Defined

`boost/graph/planar_canonical_ordering.hpp`

### Parameters

IN: `Graph& g`
An undirected graph. The graph type must be a model of
VertexAndEdgeListGraph.
The graph must:
- Be maximal planar.
- Have at least two vertices.

IN: `PlanarEmbedding`
A model of PlanarEmbedding.

IN: `OutputIterator`
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)`

### Example

`examples/canonical_ordering.cpp`

### See Also

Planar Graphs in the Boost Graph Library

Copyright © 2007 Aaron Windsor (
aaron.windsor@gmail.com)