Planar Embedding Concept

A planar embedding is an important intermediate representation of a drawing of a planar graph. Instead of specifying the absolute positions of the vertices and edges in the plane, a planar embedding specifies their positions relative to one another. A planar embedding consists of a sequence, for each vertex in the graph, of all of the edges incident on that vertex in the order in which they are to be drawn around that vertex.

A planar embedding is a refinement of LValuePropertyMap that places additional restrictions the value_type used in the property map.

Notation

Associated Types

| Const Iterator | boost::property_traits<Embedding>::value_type::const_iterator | The iterator type used to iterate over the ordering of the edges in the planar embedding of a particular vertex |

Valid Expressions

Expression	Return Type	Description
embedding[v].begin()	boost::property_traits<Embedding>::value_type::const_iterator	Returns an iterator to the beginning of the range of edges in the embedding around vertex v
embedding[v].end()	boost::property_traits<Embedding>::value_type::const_iterator	Returns an iterator to the end of the range of edges in the embedding around vertex v
embedding[v].clear()	void	Clears all edges in the embedding around a vertex v
embedding[v].push_back(e)	void	Adds an edge e to the end of the sequence of embedded edges around the vertex v

Complexity Guarantees

Starting with an empty embedding, any mixed sequence of n calls to a particular vertex's push_back and clear should take O(n) time.

Models

Any LValue property map that maps vertices to a std::vector, std::list, or std::deque models this concept. Below is an example of using this approach to create a model of PlanarEmbedding:

#include <boost/property_map/property_map.hpp>
#include <vector>

...

// Assume a graph type "Graph" defined somewhere above and
// an instance of Graph in a variable g.

// A typedef for the storage - a vector of vectors of edge descriptors
typedef
    std::vector< std::vector< graph_traits<Graph>::edge_descriptor > >
    planar_embedding_storage_t;

// A typedef for the iterator property map, assuming the graph has
// an interior vertex index map
typedef
    boost::iterator_property_map< planar_embedding_storage_t::iterator,
                                  property_map<Graph, vertex_index_t>::type
                                >
    planar_embedding_t;

// Create an instance of the storage and the property map
planar_embedding_storage_t planar_embedding_storage(num_vertices(g));
planar_embedding_t planar_embedding(planar_embedding_storage.begin(),
                                    get(vertex_index, g)
                                    );

// planar_embedding can now be passed to any function expecting a model
// of PlanarEmbedding.