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

Abstract

We prove that the Max-Cut and Max-Bisection problems are NP-hard on unit disk graphs. We also show that $\lambda$-precision graphs are planar for $\lambda$ > 1 / \sqrt{2}$.