Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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$?
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.
