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

الأصل · EN

We 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 / √2.