Cut Polytopes of Minor-free Graphs

Abstract

The cut polytope of a graph $G$ is the convex hull of the indicator vectors of all cuts in $G$ and is closely related to the MaxCut problem. We give the facet-description of cut polytopes of $K_{3,3}$-minor-free graphs and introduce an algorithm solving MaxCut on those graphs, which only requires the running time of planar MaxCut. Moreover, starting a systematic geometric study of cut polytopes, we classify graphs admitting a simple or simplicial cut polytope.

15 pages, 2 figures, 1 table