# Graphs that are not $\mathbb{R}^2$-realizable

We say that a finite, simple, undirected graph $$G=(V,E)$$ is $$\mathbb{R}^2$$-realizable if there is an injective map $$\varphi:V\to \mathbb{R}^2$$ such that for $$v\neq w \in V$$ we have $$\{v,w\} \in E$$ if and only if $$|\varphi(v)-\varphi(w)| < 1$$ where $$|\cdot|$$ denotes the Euclidean distance.

What is an example of a finite graph that is not $$\mathbb{R}^2$$-realizable?

• Those are precisely the unit disk graphs (to replace the inequality by a strict one, scale the graph by a factor slightly smaller than $1$). – Wojowu Feb 12 at 15:29

## 1 Answer

How about the star $$S_6$$? To realize this graph in the way you describe, you would have to map the center point to some $$c \in \mathbb R^2$$; then you would need to map the $$6$$ other points of $$S_6$$ inside the unit circle around $$c$$, but all at distance $$\geq\!1$$ from each other. This is impossible.