Wrapper for Boyer’s (C) planarity algorithm.

sage.graphs.planarity.is_planar(g, kuratowski=False, set_pos=False, set_embedding=False, circular=False)

Check whether g is planar using Boyer’s planarity algorithm.

If kuratowski is False, returns True if g is planar, False otherwise. If kuratowski is True, returns a tuple, first entry is a boolean (whether or not the graph is planar) and second entry is a Kuratowski subgraph, i.e. an edge subdivision of \(K_5\) or \(K_{3,3}\) (if not planar) or None (if planar). Also, will set an _embedding attribute for the graph g if set_embedding is set to True.

INPUT:

  • kuratowski – boolean (default: False); when set to True, return a tuple of a boolean and either None or a Kuratowski subgraph (i.e. an edge subdivision of \(K_5\) or \(K_{3,3}\)). When set to False, returns True if g is planar, False otherwise.
  • set_pos – boolean (default: False); whether to use Schnyder’s algorithm to determine and set positions
  • set_embedding – boolean (default: False); whether to record the combinatorial embedding returned (see get_embedding())
  • circular – boolean (default: False); whether to test for circular planarity

EXAMPLES:

sage: G = graphs.DodecahedralGraph()
sage: from sage.graphs.planarity import is_planar
sage: is_planar(G)
True
sage: Graph('@').is_planar()
True