Max-Cut Party Splitter PLANAR

Split a "who argues with whom" graph into two teams to maximize total crossing conflict weight (classic weighted Max-Cut). Grounded in arXiv:2606.28478 "Maximum Cut Algorithms and Upper Bounds for Planar and Toroidal Graphs": the base graph here is a genuine maximal planar triangulation (straight-line, provably zero edge crossings — the same structure Hadlock's planar Max-Cut algorithm exploits). Click "Go Toroidal" to add extra long-range edges and watch a planar-style algorithm's answer become only an upper bound, not the true optimum.
Your current cut
0
Optimal (planar)
—
Team A Team B Rivalry edge (+weight, thicker = stronger) Friendship edge (−weight) Wrap-around / toroidal edge

How to play

Click any node to toggle it between Team A (blue) and Team B (orange). Drag nodes to rearrange the drawing (this is just a re-drawing of the same planar embedding — no crossings are added or removed by dragging).

"Your current cut" updates live as the sum of edge weights crossing the two teams. Click Reveal Optimal Cut to see the true maximum, computed by exhaustive brute force — exact, not a heuristic, for graphs this size.

Click Go Toroidal to add a few extra gold "wrap-around" edges — connections that only make sense once you glue opposite ends of the drawing together like a donut, giving the graph genus 1 instead of genus 0 (planar). The demo then shows the gap between a naive planar-style bound and the true toroidal max-cut.

Why the bound is real math

Bound = (optimal cut restricted to the planar edges only) + (sum of the positive-weight wrap edges, each optimistically assumed to be cuttable). For any team split S: cut(S, full graph) = cut(S, planar edges) + cut(S, wrap edges) ≤ maxcut(planar edges) + Σmax(w,0). That's a provable upper bound on the true toroidal optimum — exactly the phenomenon in the paper: a planar-style algorithm that can't see the extra topology overestimates.