# Planar max-cut

## Contents |

### Introduction

A cut in a weighted undirected graph *G* = (*V*,*E*) is defined by vertex set *S*⊆*V* as the set of all edges with exactly one endpoint
in *S*. The weight of a cut is the sum of the weights of its edges. Now, the max-cut problem is to find a cut of *G* with maximum weight.
There has been a lot of interest in max-cut problems. These problems have many applications, cf. ground state calculations of Ising spin glasses,
but are hard to solve in general.

But, there exist a few special cases that can be solved efficiently. One is the case if the underlying graph is planar.

It was shown independently by [Hadlock (1975)] and by
[Dorfman and Orlova (1972)] that max-cut on planar graphs is equivalent to finding eulerian subgraphs
in its dual graph.

Later on [Bieche et al. (1980)], [Barahona (1982,1983,1993)] [Barahona et al. (1982)],

refined these ideas further and showed that max-cut on graphs not contractible to *K*_{5} can be solved in polynomial time today.

### The method

In [Barahona (1993)] it is exploited that a graph not contractible to *K*_{5} can be decomposed

*V*

_{8}and this

can be used to find a max-cut in graphs not contractible to *K*_{5}.
The max-cut on the graph *V*_{8} is solved by enumeration and on the planar graph the problem is solved by following a general scheme that is common to
many solution approaches. We state here this scheme:

### General scheme

**Algorithm:** *Max-cut on planar graphs*

- build dual graph
*G*_{d}of the planar input graph*G* - transform
*G*_{d}in an appropriate way to build an auxilliary graph*G*_{t} - calculate an optimum weight perfect matching
*M*in*G*_{t} *M*induces an eulerian subgraph*G*_{d}[*E**u**l**e**r*] in*G*_{d}*G*_{d}[*E**u**l**e**r*] corresponds to a max-cut in*G*

Roughly speaking the algorithms follow the same algorithmic scheme, that we stated in the above pseudocode.

Being more concrete, at first the dual graph is constructed which is then transformed to an auxilliary graph such that an optimum weighted perfect matching in this auxilliary graph yields subgraphs in the dual, such that each vertex has even degree. In fact those subgraphs are Eulerian and by the known one-to-one correspondence between max-cut in the primal graph and eulerian subgraphs in its dual graph the problem can be solved by the matching computation.

As this general scheme is common to many approaches solving max-cut on planar graphs and fast implementation exists that solves the problem for graphs with million of nodes, which use fast matching procedures that build on the planar seperator theorem stated by [Lipton, Tarjan (1979)], cf. [Pardella, Liers (2008)] and [Liers, Pardella (2008)].

### Example

Consider as an example the planar drawing of a graph *G* = (*V*,*E*) in the following figure.

*G* consists of seven vertices *V* = {1,2,...7} and eight faces *V*_{D} = {*A*,*B*,...*H*}.
Vertices are labeled with numbers and faces with capital letters. Edge weights are given as edge
subscripts.

A matching on a (not shown) appropriated auxilliary graph would then e.g. yield the shown optimum-weight Eulerian subgraph of the dual as the blue edges form a simple cycle forming the edge set of the induced subgraph, and thus a max-cut of the primal graph.

The cut edges are coloured red and the corresponding Eulerian subgraph in the dual is depicted in blue. The green vertices belong to the same partition.