make_maximal_planar

Adds edges to a biconnected planar graph to make it maximal planar.

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

Example

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

using namespace boost;

struct Edge { int idx; };

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

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

void reembed(Graph& g, std::vector<std::vector<Descriptor>>& s) {
    s.assign(num_vertices(g), {});
    auto emb = make_iterator_property_map(s.begin(), get(vertex_index, g));
    boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
        boyer_myrvold_params::embedding = emb);
}

int main() {
    Graph g(4);
    add_edge(0, 1, g); add_edge(1, 2, g); add_edge(2, 3, g);

    std::vector<std::vector<Descriptor>> st(num_vertices(g));
    reindex(g); reembed(g, st);
    auto emb = make_iterator_property_map(st.begin(), get(vertex_index, g));
    boost::graph::make_biconnected_planar(g, emb, get(&Edge::idx, g));

    reindex(g); reembed(g, st);
    emb = make_iterator_property_map(st.begin(), get(vertex_index, g));
    std::cout << "Edges before: " << num_edges(g) << "\n";
    boost::graph::make_maximal_planar(g, emb, get(vertex_index, g), get(&Edge::idx, g));
    std::cout << "Edges after make_maximal_planar: " << num_edges(g) << "\n";
}
Edges before: 5
Edges after make_maximal_planar: 6

Positional version

namespace boost::graph {
template<typename Graph, typename PlanarEmbedding,
         typename VertexIndexMap, typename EdgeIndexMap,
         typename AddEdgeVisitor>
void make_maximal_planar(
    Graph& g,
    PlanarEmbedding embedding,
    VertexIndexMap vm,
    EdgeIndexMap em,
    AddEdgeVisitor vis);
}
Direction Parameter Description

IN/OUT

Graph& g

An undirected graph. The graph type must be a model of Vertex List Graph, Incidence Graph, and a Mutable Graph.

IN

PlanarEmbedding embedding

A Readable Property Map that models the PlanarEmbedding concept.

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)

IN

EdgeIndexMap em

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

IN

AddEdgeVisitor vis

A model of AddEdgeVisitor. The visitor is passed by value, so the algorithm works on a copy. Wrap it in std::ref(vis) to have your own visitor updated in place.
Default: default_add_edge_visitor, a class that defines visit_vertex_pair to dispatch its calls to add_edge.

Migrating from boost::make_maximal_planar

The boost::make_maximal_planar overloads are deprecated. They took the visitor by non-const reference, which rejected temporaries and differed from the other BGL algorithms. Removal planned for Boost 1.95. Calls left unchanged then fail to compile instead of silently changing behavior.

  1. Replace boost::make_maximal_planar with boost::graph::make_maximal_planar. Unqualified calls need qualifying too, since argument dependent lookup only finds the deprecated overloads.

  2. The deprecated overload already worked on a copy of the visitor, so no other change is needed. To read the visitor’s state after the call, pass it as std::ref(vis).

// Before
make_maximal_planar(g, embedding, get(vertex_index, g), get(edge_index, g), my_visitor);

// After
boost::graph::make_maximal_planar(g, embedding, get(vertex_index, g), get(edge_index, g), my_visitor);

boost::make_maximal_planar (deprecated)

Deprecated: use boost::graph::make_maximal_planar. Removal planned for Boost 1.95. See the migration steps.

 
namespace boost {
template <typename Graph, typename PlanarEmbedding, typename VertexIndexMap, typename EdgeIndexMap, typename AddEdgeVisitor>
void make_maximal_planar(Graph& g, PlanarEmbedding embedding, VertexIndexMap vm, EdgeIndexMap em, AddEdgeVisitor& vis);

template <typename Graph, typename PlanarEmbedding, typename VertexIndexMap, typename EdgeIndexMap>
void make_maximal_planar(Graph& g, PlanarEmbedding embedding, VertexIndexMap vm, EdgeIndexMap em);

template <typename Graph, typename PlanarEmbedding, typename VertexIndexMap>
void make_maximal_planar(Graph& g, PlanarEmbedding embedding, VertexIndexMap vm);

template <typename Graph, typename PlanarEmbedding>
void make_maximal_planar(Graph& g, PlanarEmbedding embedding);
}

Description

A planar graph G is maximal planar if no additional edges (except parallel edges and self-loops) can be added to G without creating a non-planar graph. By Euler’s formula, a maximal planar graph on n vertices (n > 2) always has 3n - 6 edges and 2n - 4 faces. The input graph to make_maximal_planar must be a biconnected planar graph with at least 3 vertices.

The default behavior of make_maximal_planar is to modify the graph g by calling add_edge(u,v,g) for every pair of vertices (u,v) where an edge needs to be added to make g maximal planar. This behavior can be overridden by providing a visitor as the AddEdgeVisitor parameter. The only requirement for an AddEdgeVisitor is that it define a member function with the following signature:

template<typename Graph, typename Vertex>
void visit_vertex_pair(Vertex u, Vertex v, Graph& g);

This event point can also be used as a hook to update the underlying edge index map automatically as edges are added. See the documentation for the AddEdgeVisitor concept for more information.

See also examples/make_maximal_planar.cpp.