Max-Cut and Max-Bisection are NP-hard on unit disk graphs
<|reference_start|>Max-Cut and Max-Bisection are NP-hard on unit disk graphs: 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}$.<|reference_end|>
@article{diaz2006max-cut,
    title={Max-Cut and Max-Bisection are NP-hard on unit disk graphs},
    author={Josep Diaz and Marcin Kaminski},
    journal={arXiv preprint arXiv:cs/0609128},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0609128},
    primaryClass={cs.DS cs.CC}
}