`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));
    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";
    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

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

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. Default: `default_add_edge_visitor`, a class that defines `visit_vertex_pair` to dispatch its calls to `add_edge`.

IN/OUT

Graph& g

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

PlanarEmbedding embedding

A Readable Property Map that models the PlanarEmbedding concept.

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)

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)

AddEdgeVisitor vis

A model of AddEdgeVisitor.
Default: default_add_edge_visitor, a class that defines visit_vertex_pair to dispatch its calls to add_edge.

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.

Edit this Page