is_planar#
- graph_tool.topology.is_planar(g, embedding=False, kuratowski=False)[source]#
Test if the graph is planar.
- Parameters:
- g
Graph
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.
- g
- Returns:
- is_planarbool
Whether or not the graph is planar.
- embedding
VertexPropertyMap
(only if embedding=True) A vertex property map with the out-edges indices in clockwise order in the planar embedding,
- kuratowski
EdgePropertyMap
(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") <...>