make_maximal_planar

make_maximal_planar#

graph_tool.topology.make_maximal_planar(g)[source]#

Add edges to the graph to make it maximally planar.

Parameters:
gGraph

Graph to be used. It must be a biconnected planar graph with at least 3 vertices.

Notes

A graph is maximal planar if no additional edges can be added to it without creating a non-planar graph. By Euler’s formula, a maximal planar graph with V > 2 vertices always has 3V - 6 edges and 2V - 4 faces.

The input graph to make_maximal_planar() must be a biconnected planar graph with at least 3 vertices.

This algorithm runs in \(O(V + E)\) time.

References

Examples

>>> g = gt.lattice([10, 10])
>>> gt.make_maximal_planar(g)
>>> gt.is_planar(g)
True
>>> print(g.num_vertices(), g.num_edges())
100 294
>>> pos = gt.planar_layout(g)
>>> gt.graph_draw(g, pos, output="maximal_planar.pdf")
<...>
../_images/maximal_planar.png

A maximally planar graph.#