0
$\begingroup$

Given a graph $(V,E)$, I'm interested in embedding it into a Euclidean space $\mathbb{R}^n$ such that each vertex $v\in V$ becomes a point $x_v\in\mathbb{R}^n$ and $d(x_v,x_u) \leq 1$ (Euclidean distance) iff $(v,u) \in E$.

I know that Maxcut isn't NP-hard for planar graphs. But what if I consider graphs that can be embedded as above in $\mathbb{R}^2$, do we know if Maxcut is NP-hard in this case? What about the above embedding in $\mathbb{R}^3$?

$\endgroup$

1 Answer 1

2
$\begingroup$

A graph with $d = 2$ representation is called a unit disk graph.

The max-cut problem on unit disk graphs is NP-hard [1], even if the planar representation is given as an input.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.