|
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.
NumberOfFaces(G) : GrphMultUnd -> 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 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.
The purpose of the example is to show the embedding and faces
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 > ]
]
We show how to construct the dual graph D of a planar graph G
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;
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|