Max-Cut and Max-Bisection are NP-hard on unit disk graphs

2026-07-072026-07-07http://salesiana.dossiersoluciones.com/handle/123456789/116171We prove that the Max-Cut and Max-Bisection problems are NP-hard on unit disk graphs. We also show that $λ$-precision graphs are planar for $λ$ > 1 / \sqrt{2}$.Data Structures and AlgorithmsComputational ComplexityMax-Cut and Max-Bisection are NP-hard on unit disk graphstext