Planar Canonical Orderingtemplate <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 v1, v2, ..., vn of the vertices of a maximal planar graph having the property that, for each k, 3 <= k < n, the graph induced by v1, v2, ..., vk
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. ComplexityIf 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 Definedboost/graph/planar_canonical_ordering.hpp ParametersIN: Graph& gAn undirected graph. The graph type must be a model of VertexAndEdgeListGraph.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) ) Exampleexamples/canonical_ordering.cpp See Also
Planar Graphs in the Boost Graph Library
Copyright ? 2007 Aaron Windsor ( aaron.windsor@gmail.com) |