A linear-time algorithm due to Boyer and Myrvold [BM01] has been implemented to test if a graph is planar, and to identify a Kuratowski subgraph if the graph is non-planar. This algorithm requires that the graph has a sparse representation.
The interest of this new algorithm is that it is very easy to implement when compared to previous linear-time planarity testers. In addition, the algorithm also isolates a Kuratowski subgraph, if any, in linear-time.
The concept underlying the tester is deceptively simple: the idea is to perform a depth first search of the graph and then to try to embed (by post-order traversal of the tree) the back edges from a vertex v to its descendants in such a way that they do not cross and such that vertices with connections to ancestors of v remain along the external face.
To decide the order in which to embed back edges from v to its descendants, the external faces of components rooted by children of v are explored top-down, avoiding paths containing vertices with ancestor connections. To decide whether a vertex u has ancestor connections and must therefore be kept on the external face, one only needs the least ancestor directly adjacent to u and the lowpoint information for the children of u that are separable from the parent of u in the partial embedding.
Each back edge [w, v] is added as soon as the descendant endpoint w is encountered. If w is not in the same biconnected component as v, then the biconnected components encountered during the traversal are merged at their respective cut vertices since the new edge [w, v] biconnects them. The merge is performed such that vertices with ancestor connections remain on the external face of the newly formed biconnected component.
Traversal is terminated when all back edges from v to its descendants are added or when the external face traversal is prevented from reaching the descendant endpoint of a back edge. This occurs when both external face paths extending from the least numbered vertex in a biconnected component contain vertices with ancestor connections that block further traversal to a vertex that is the descendant endpoint w of a back edge [w, v]. In this case, a Kuratowski subgraph is isolated based primarily on ancestor connections, external face paths and depth first search tree paths.
Magma is deeply grateful for the valuable help and collaboration from the authors of [BM01], in particular John Boyer.
Tests whether the (undirected) graph G is planar. The graph may be disconnected. If the graph is non-planar then a Kuratowski subgraph of G is returned: That is, a subgraph of G homeomorphic to K5 or K3, 3. The support and vertex/edge decorations of G are not retained in this (structural) subgraph.
Returns a Kuratoswki obstruction if the graph is non-planar, or the empty graph if the graph is planar. The Kuratoswki is a (structural) subgraph of G; the support and vertex/edge decorations of G are not transferred to it.
Graph: MonStgElt Default:
Tests if a graph is homeomorphic to either K5 or K3, 3. The parameter Graph must be set to either "K5" or "K33"; it has no default setting.
Returns the faces of the planar graph G as sequences of the edges bordering the faces of G. If G is disconnected, then the face defined by an isolated vertex v is given as [ v ].
Returns the face of the planar graph G bordered by the directed edge [u, v] as an ordered list of edges of G.Note that a directed edge and an orientation determine a face uniquely: We can assume without loss of generality that the plane is given a clockwise orientation. Then given a directed edge e = [u1, v1], the face defined by e is the ordered set of edges [u1, v1], [u2, v2], ..., [um, vm] such that vi = ui + 1 for all i, 1 ≤i < m, vm = u1, and for each vi = ui + 1, the neighbours of vi, ui and vi + 1, are consecutive vertices in vi's adjacency list whose order is anti-clockwise.
Let e be the edge (u, v) of the planar graph G (recall that G is undirected). Then Face((u, v)) returns the face bordered by the directed edge [u, v] as a sequence of edges of G.
Returns the number of faces of the planar graph G. In the case of a disconnected graph, an isolated vertex counts for one face.
Returns the graph G's planar embedding as a sequence S where S[i] is a sequence of edges incident from vertex i.
Returns the ordered list of edges (in clockwise order say) incident from vertex v.
Constructs the dual G' of a planar graph G. The numbering of the vertices of G' corresponds to the order of the faces as returned by Faces(G).
> G := Graph< 5 | [ {2, 3, 5}, {1, 5}, {1}, , {1, 2} ] >;
> G;
Graph
Vertex Neighbours
1 2 3 5 ;
2 1 5 ;
3 1 ;
4 ;
5 1 2 ;
> IsConnected(G);
false
> IsPlanar(G);
true
> Faces(G);
[
[ {1, 2}, {2, 5}, {5, 1} ],
[ {1, 5}, {5, 2}, {2, 1}, {1, 3}, {3, 1} ],
[ 4 ]
]
> Embedding(G);
[
[ {1, 2}, {1, 5}, {1, 3} ],
[ {2, 5}, {2, 1} ],
[ {3, 1} ],
[],
[ {5, 1}, {5, 2} ]
]
> Embedding(VertexSet(G)!1);
[ {1, 2}, {1, 5}, {1, 3} ]
Now let's turn to a simple non-planar graph whose obstruction is
K3, 3:
> G := Graph< 6 | [ {3, 4, 5}, {3, 4, 5, 6}, {1, 2, 5, 6},
> {1, 2, 5, 6}, {1, 2, 3, 4, 6}, {2, 3, 4, 5} ] >;
> G;
Graph
Vertex Neighbours
1 3 4 5 ;
2 3 4 5 6 ;
3 1 2 5 6 ;
4 1 2 5 6 ;
5 1 2 3 4 6 ;
6 2 3 4 5 ;
> IsPlanar(G);
false
> b, O := IsPlanar(G);
> IsSubgraph(G, O);
true
> O;
Graph
Vertex Neighbours
1 4 5 3 ;
2 3 5 4 ;
3 1 6 2 ;
4 2 6 1 ;
5 6 1 2 ;
6 5 4 3 ;
> IsHomeomorphic(O : Graph := "K33");
true