Planar Graphs

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.

IsPlanar(G): GrphMultUnd -> BoolElt, GrphMultUnd

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 \(K_5\) or \(K_{3, 3}\). The support and vertex/edge decorations of \(G\) are not retained in this (structural) subgraph.

Obstruction(G): GrphMultUnd -> GrphMultUnd

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.

IsHomeomorphic(G: parameters): GrphMultUnd -> BoolElt

Graph: MonStg                    Default: 

Tests if a graph is homeomorphic to either \(K_5\) or \(K_{3,3}\). The parameter Graph must be set to either “K5” or “K33”; it has no default setting.

Faces(G): GrphMultUnd -> SeqEnum[GrphVert]

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 ]\).

Face(u, v): GrphVert, GrphVert -> SeqEnum

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 = [u_1, v_1]\), the face defined by \(e\) is the ordered set of edges \([u_1, v_1], [u_2, v_2], \ldots, [u_m, v_m]\) such that \(v_i = u_{i+1}\) for all \(i\), \(1 \leq i < m\), \(v_m = u_1\), and for each \(v_i = u_{i+1}\), the neighbours of \(v_i\), \(u_i\) and \(v_{i+1}\), are consecutive vertices in \(v_i\)’s adjacency list whose order is anti-clockwise.

Face(e): GrphEdge -> SeqEnum

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\).

NFaces(G): GrphMultUnd -> RngIntElt

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.

Embedding(G): GrphMultUnd -> SeqEnum

Returns the planar embedding of the graph \(G\) as a sequence \(S\) where \(S[i]\) is a sequence of edges incident from vertex \(i\).

Embedding(v): GrphVert -> SeqEnum

Returns the ordered list of edges (in clockwise order say) incident from vertex \(v\).

Example: GrphMult Planar (ex-c07270)

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 > ]
]

Run in calculatorCopy input

Example: GrphMult Planar Dual (ex-d8a2c8)

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 \(f_i\) is adjacent to face \(f_2\) if and only if \(f_1\) and \(f_2\) 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)] >;

Run in calculatorCopy input

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 >

Run in calculatorCopy input

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 \(E^{\ast} = \{ e^{\ast} : e \in E \}\) is a minimal cut in \(D\). For more details, see [Diestel, 2000, \$ 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;

Run in calculatorCopy input