is_planar

Contents

is_planar#

graph_tool.topology.is_planar(g, embedding=False, kuratowski=False)[source]#

Test if the graph is planar.

Parameters:
gGraph

Graph to be used.

embeddingbool (optional, default: False)

If true, return a mapping from vertices to the clockwise order of out-edges in the planar embedding.

kuratowskibool (optional, default: False)

If true, the minimal set of edges that form the obstructing Kuratowski subgraph will be returned as a property map, if the graph is not planar.

Returns:
is_planarbool

Whether or not the graph is planar.

embeddingVertexPropertyMap (only if embedding=True)

A vertex property map with the out-edges indices in clockwise order in the planar embedding,

kuratowskiEdgePropertyMap (only if kuratowski=True)

An edge property map with the minimal set of edges that form the obstructing Kuratowski subgraph (if the value of kuratowski[e] is 1, the edge belongs to the set)

Notes

A graph is planar if it can be drawn in two-dimensional space without any of its edges crossing. This algorithm performs the Boyer-Myrvold planarity testing [boyer-myrvold]. See [boost-planarity] for more details.

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

References

[boyer-myrvold]

John M. Boyer and Wendy J. Myrvold, “On the Cutting Edge: Simplified O(n) Planarity by Edge Addition” Journal of Graph Algorithms and Applications, 8(2): 241-273, 2004. http://www.emis.ams.org/journals/JGAA/accepted/2004/BoyerMyrvold2004.8.3.pdf

Examples

>>> from numpy.random import random
>>> g = gt.triangulation(random((100,2)))[0]
>>> p, embed_order = gt.is_planar(g, embedding=True)
>>> print(p)
True
>>> print(list(embed_order[g.vertex(0)]))
[0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 1]
>>> g = gt.random_graph(100, lambda: 4, directed=False)
>>> p, kur = gt.is_planar(g, kuratowski=True)
>>> print(p)
False
>>> g.set_edge_filter(kur)
>>> gt.graph_draw(g, output="kuratowski.pdf")
<...>
../_images/kuratowski.png

Obstructing Kuratowski subgraph of a random graph.#

Contents