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?

  • 5
    $\begingroup$ 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$). $\endgroup$ – Wojowu Feb 12 at 15:29

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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