The planarity algorithm implemented in Magma tests whether an undirected graph or multigraph is planar. If the graph is planar, then an embedding of the graph is produced, otherwise a Kuratowski subgraph is identified. For a thorough discussion of this algorithm, its implementation and complexity, the reader is referred to Section Planar Graphs.
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 graph is returned as a (structural) subgraph of G; the support and vertex/edge decorations are not retained.
Graph: MonStg 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 planar embedding of the graph G 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.
of a graph with multiples edges and loops.
> G := MultiGraph< 3 | < 1, {2, 3} >, < 1, {2} >, < 2, {2, 3} > >;
> G;
Multigraph
Vertex Neighbours
1 2 3 2 ;
2 3 2 2 1 1 ;
3 2 1 ;
> IsPlanar(G);
true
> Faces(G);
[
[ < {1, 2}, 5 >, < {2, 1}, 1 > ],
[ < {1, 2}, 1 >, < {2, 2}, 7 >, < {2, 3}, 9 >, < {3, 1}, 3 > ],
[ < {1, 3}, 3 >, < {3, 2}, 9 >, < {2, 1}, 5 > ],
[ < {2, 2}, 7 > ]
]
> Embedding(G);
[
[ < {1, 2}, 5 >, < {1, 2}, 1 >, < {1, 3}, 3 > ],
[ < {2, 3}, 9 >, < {2, 2}, 7 >, < {2, 1}, 1 >, < {2, 1}, 5 > ],
[ < {3, 1}, 3 >, < {3, 2}, 9 > ]
]
and how to find all its minimal cuts. The vertex set of the dual is the set of faces F of G where face fi is adjacent to face f2 if and only if f1 and f2 share a common edge in G. For the purpose of this example a cut of a graph G is defined as a set of edges which disconnects G.
Let us construct a small planar graph G and its dual D. For clarity, the support of D will be the standard support (we could have chosen it to be the set of faces of G).
> G := MultiGraph< 4 | {1, 2}, {1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}>;
> IsPlanar(G);
true
> Faces(G);
[
[ < {1, 3}, 5 >, < {3, 2}, 7 >, < {2, 1}, 3 > ],
[ < {1, 2}, 3 >, < {2, 1}, 1 > ],
[ < {1, 2}, 1 >, < {2, 4}, 9 >, < {4, 3}, 11 >, < {3, 1}, 5 > ],
[ < {3, 4}, 11 >, < {4, 2}, 9 >, < {2, 3}, 7 > ]
]
> F := {@ SequenceToSet(f) : f in Faces(G) @};
> D := MultiGraph< #F | >;
> mapG2D := [ 0 : i in [1..Max(Indices(G))] ];
> mapD2G := [ 0 : i in [1..Max(Indices(G))] ];
> for u in VertexSet(D) do
> for v in VertexSet(D) do
> if Index(v) le Index(u) then
> continue;
> end if;
> M := F[ Index(u) ] meet F[ Index(v) ];
> for e in M do
> D, edge :=
> AddEdge(D, VertexSet(D)!u, VertexSet(D)!v);
>
> mapG2D[Index(e)] := Index(edge);
> mapD2G[Index(edge)] := Index(e);
> end for;
> end for;
> end for;
>
> e_star := map< EdgeSet(G) -> EdgeSet(D) |
> x :-> EdgeSet(D).mapG2D[Index(x)],
> y :-> EdgeSet(G).mapD2G[Index(y)] >;
The map e-star is the bijection from G's edge-set into
D's edge-set:
> for e in EdgeSet(G) do
> e, " ", e @ e_star;
> end for;
< {1, 3}, 5 > < {1, 3}, 3 >
< {1, 2}, 3 > < {1, 2}, 1 >
< {1, 2}, 1 > < {2, 3}, 7 >
< {2, 4}, 9 > < {3, 4}, 11 >
< {2, 3}, 7 > < {1, 4}, 5 >
< {3, 4}, 11 > < {3, 4}, 9 >
>
> for e in EdgeSet(D) do
> e, " ", e @@ e_star;
> end for;
< {1, 4}, 5 > < {2, 3}, 7 >
< {1, 3}, 3 > < {1, 3}, 5 >
< {1, 2}, 1 > < {1, 2}, 3 >
< {2, 3}, 7 > < {1, 2}, 1 >
< {3, 4}, 11 > < {2, 4}, 9 >
< {3, 4}, 9 > < {3, 4}, 11 >
If G is biconnected, then any of its faces
is bounded by a cycle.
From Euler's formula giving the number of faces in a graph,
we deduce that the boundaries of the internal faces of G,
which form a chordless cycle, form a basis for the cycle space of
G.
It is a well-known fact that, if G is connected and planar, a set of edges E is the set of edges of a cycle in G if and only if East = { east : e ∈E } is a minimal cut in D. For more details, see [Die00, $ 4].
From this we conclude that we can compute the minimal cuts generating the cut space of the dual graph D. We verify that G is biconnected, we compute the cut corresponding to each face of G, and verify that it is a minimal cut. All the cuts together form a generating set of the cut space of D. Had we not included the cut corresponding to the external face of G, we would have a basis of the cut space.
> IsBiconnected(G);
true
> for f in F do
> Cut := { e @ e_star : e in f };
> H := D;
> RemoveEdges(~H, Cut);
> assert not IsConnected(H);
>
> for e in Cut do
> C := Exclude(Cut, e);
> H := D;
> RemoveEdges(~H, C);
> assert IsConnected(H);
> end for;
> end for;