Short answer Your problem is exactly the weighted correlation clustering objective on a (not necessarily complete) graph: you want to find a partition of the vertices so as to maximize agreements, where an agreement is “put endpoints together” on a negative-weight edge and “put endpoints apart” on a positive-weight edge. Formally, if we let A be the total weight of agreements A = sum_{e=(u,v), w(e)>0} w(e)·[u and v in different parts] + sum_{e=(u,v), w(e)<0} |w(e)|·[u and v in the same part], then your objective (minimize the sum of weights of monochromatic edges) is exactly sum_{e=(u,v)} w(e)·[u and v in the same part] = (sum_{w(e)>0} w(e)) − A, so minimizing your objective is equivalent to maximizing A.

For planar graphs, maximizing agreements (i.e., correlation clustering) is NP-hard (even with unit weights), but admits a PTAS (polynomial-time approximation scheme).

Details and consequences

• Equivalence to correlation clustering.

  • If w(e)>0, you prefer to separate the endpoints to avoid paying w(e) when they are in the same part.
  • If w(e)<0, you prefer to keep endpoints together to collect the negative contribution (which lowers the objective).
  • Up to the additive constant sum_{w>0} w(e), your objective is the standard “maximize agreements” correlation clustering objective with weights |w(e)| and signs given by s(e)=−sign(w(e)).

• Complexity on planar graphs.

  • NP-hardness: Correlation clustering (maximize agreements / minimize disagreements) remains NP-hard on planar graphs. Consequently, your problem is NP-hard on planar graphs as well (via the equivalence above).
  • Approximation: There is a PTAS for correlation clustering on planar graphs (and more generally on minor-free graphs) using Baker-type decomposition combined with dynamic programming on bounded treewidth subgraphs. By the same equivalence, your problem also admits a PTAS.

• Special/easy cases.

  • If you restrict to exactly two colors, your objective becomes sum_{e same} w(e) = sum_{e} w(e) − sum_{e cut} w(e), so minimizing it is equivalent to maximizing a weighted cut. On planar graphs, weighted Max-Cut is solvable in polynomial time; thus the two-color restriction is polytime on planar graphs.
  • If all weights are nonnegative, the optimal value is 0 (color every vertex differently).
  • If all weights are nonpositive, the best is to color each connected component with a single color (to include all negative edges).
  • For fixed ε>0, an exact solution on graphs of treewidth O(1/ε) can be found by dynamic programming over a tree decomposition with states that encode partitions of a bag; combining this with Baker’s layering yields a PTAS.

What this gives you

• Decision/optimization: NP-hard in general even for planar inputs with weights in {−1,+1}.
• Approximation: PTAS on planar graphs.
• Exact polynomial algorithms: Only for special cases (e.g., two colors, all weights one-signed, bounded treewidth, or tiny subfamilies).

If you need pointers to concrete algorithmic frameworks for the PTAS (Baker-style decomposition and DP for pairwise potentials/Potts-like models) or to implementable exact solvers on bounded-treewidth decompositions, I can outline them.