|
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.
NumberOfFaces(G) : GrphUnd -> RngIntElt
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).
We start with a small disconnected planar graph G:
Notice how one of the faces of G is defined by the isolated
vertex 4.
> 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
K 3, 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
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|