Planar Face Traversal

template<typename Graph, typename PlanarEmbedding, typename PlanarFaceVisitor, typename EdgeIndexMap>
void planar_face_traversal(const Graph& g, PlanarEmbedding embedding, PlanarFaceVisitor& visitor, EdgeIndexMap em);

A graph is planar if it can be drawn in two-dimensional space with no two of its edges crossing. Any embedding of a planar graph separates the plane into distinct regions that are bounded by sequences of edges in the graph. These regions are called faces.

A plane drawing of a graph (left), and the 8 faces defined by the planar embedding (right.) Each connected blue region in the image on the right is a face. The large blue region surrounding the graph is the outer face.

A traversal of the faces of a planar graph involves iterating through all faces of the graph, and on each face, iterating through all vertices and edges of the face. The iteration through all vertices and edges of each face follows a path around the border of the face.

In a biconnected graph, like the one shown above, each face is bounded by a cycle and each edge belongs to exactly two faces. For this reason, when planar_face_traversal is called on a biconnected graph, each edge will be visited exactly twice: once on each of two distinct faces, and no vertex will be visited more than once on a particular face. The output of planar_face_traversal on non-biconnected graphs is less intuitive - for example, if the graph consists solely of a path of vertices (and therefore a single face), planar_face_traversal will iterate around the path, visiting each edge twice and visiting some vertices more than once. planar_face_traversal does not visit isolated vertices.

Like other graph traversal algorithms in the Boost Graph Library, the planar face traversal is a generic traversal that can be customized by the redefinition of certain visitor event points. By defining an appropriate visitor, this traversal can be used to enumerate the faces of a planar graph, triangulate a planar graph, or even construct a dual of a planar graph.

For example, on the above graph, an instance my_visitor of the following visitor:

    struct output_visitor: public planar_face_traversal_visitor
    {
        void begin_face() { std::cout << "New face: "; }
        template <typename Vertex> void next_vertex(Vertex v) { std::cout << v << " "; } 
        void finish_face() { std::cout << std::endl; }
    };

can be passed to the planar_face_traversal function:

    output_visitor my_visitor;
    planar_face_traversal(g, embed, my_visitor); //embed is a planar embedding of g

and might produce the output

    New face: 1 2 5 4
    New face: 2 3 4 5
    New face: 3 0 1 4
    New face: 1 0 3 2

Visitor Event Points

visitor.begin_traversal(): called once before any faces are visited.
visitor.begin_face(): called once, for each face, before any vertex or edge on that face has been visited.
visitor.end_face(): called once, for each face, after all vertices and all edges on that face have been visited.
visitor.next_vertex(Vertex v): called once on each vertex in the current face (the start and end of which are designated by calls to begin_face() and end_face(), respectively) in order according to the order established by the planar embedding.
visitor.next_edge(Edge e): called once on each edge in the current face (the start and end of which are designated by calls to begin_face() and end_face(), respectively) in order according to the order established by the planar embedding.
visitor.end_traversal(): called once after all faces have been visited.

Although next_vertex is guaranteed to be called in sequence for each vertex as the traversal moves around a face and next_edge is guaranteed to be called in sequence for each edge as the traversal moves around a face, there's no guarantee about the order in which next_vertex and next_edge are called with respect to each other in between calls to begin_face and end_face. These calls may be interleaved, all vertex visits may precede all edge visits, or vise-versa.

planar_face_traversal iterates over a copy of the edges of the input graph, so it is safe to add edges to the graph during visitor event points.

Complexity

If all of the visitor event points run in constant time, the traversal 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_face_traversal.hpp

Parameters

IN: Graph& g

An undirected graph. The graph type must be a model of VertexAndEdgeListGraph

IN: PlanarEmbedding

A model of PlanarEmbedding.

IN: PlanarFaceVisitor

A model of PlanarFaceVisitor.

IN: EdgeIndexMap vm

A Readable Property Map that maps edges from g to distinct integers in the range [0, num_edges(g) )
Default: get(edge_index,g)

Example

examples/planar_face_traversal.cpp