CutPlanar finds a minimal cut in an arbitrary planar graph, i.e., in a graph that can be embedded into the plane. Instead of an explicit embedding of vertices and edges, an algebraic embedding is used.
This embedding is given by a counter-clockwise order of all edges that are adjacent to a given vertex:
In order to compute the cut, the following steps have to be performed:
In the following sections, we explain these steps with respect to the graph sketched in the image above.
First, we have to define the algebraic embedding of the planar graph. To do this, we construct an array of 9 vertices, an array of 13 edges and an array of 6 faces (Face A, ..., Face F):
Next, we define the edges by providing a start and a target vertex as well as a left and a right face. In this example, we assume an undirected edge with unit capacity, i.e., the capacity in both directions is 1.
Finally, to every vertex a list of adjacent edges has to be provided. The edges in every list are ordered in a counter-clockwise sense.
Now, we have to compute the maximum flow. In order to do this via CutPlanar, we have to initialize CutPlanar with the planar graph as well as a source and a sink.
Finally, we have to compute the value of the maximum flow. This is the most time consuming method of the class and is called via
For most applications, we are not only interested in the value of the minimum cut, but also in the cut itself. The classical way in describing this cut is to assign a binary labeling to each vertex of the graph. This labeling can be provided via CutPlanar::getLabel or CutPlanar::getLabels
It is known that the edges of a planar cut define a closed path in the dual graph. To extract either this path or the vertices at the boundary of this path, the methods CutPlanar::getCircularPath and CutPlanar::getCutBoundary are provided
The complete code can be seen here: cutplanar.cpp.