Wrapper for Boyer’s (C) planarity algorithm.¶
-
sage.graphs.planarity.
is_planar
(g, kuratowski=False, set_pos=False, set_embedding=False, circular=False)¶ Calls Boyer’s planarity algorithm to determine whether g is planar. 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 graphg
ifset_embedding
is set to True.INPUT:
kuratowski
– IfTrue
, return a tuple of a boolean and eitherNone
or a Kuratowski subgraph (i.e. an edge subdivision of \(K_5\) or \(K_{3,3}\))set_pos
– ifTrue
, uses Schnyder’s algorithm to determine positionsset_embedding
– ifTrue
, records the combinatorial embedding returned (see g.get_embedding())circular
– ifTrue
, 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
TESTS:
We try checking the planarity of all graphs on 7 or fewer vertices. In fact, to try to track down a segfault, we do it twice.
sage: import networkx.generators.atlas # long time sage: atlas_graphs = [Graph(i) for i in networkx.generators.atlas.graph_atlas_g()] # long time sage: a = [i for i in [1..1252] if atlas_graphs[i].is_planar()] # long time sage: b = [i for i in [1..1252] if atlas_graphs[i].is_planar()] # long time sage: a == b # long time True
There were some problems with
set_pos
stability in the past, so let’s check if this this runs without exception:sage: for i,g in enumerate(atlas_graphs): # long time ....: if (not g.is_connected() or i==0): ....: continue ....: _ = g.is_planar(set_embedding=True, set_pos=True)