2
$\begingroup$

Here's a nice property about unit-disk-graphs :

Suppose $V\subseteq\mathbb{R}^2$ is a finite set of points in the plane. Build the graph $G_V=(V,E)$ such that $(v,v')\in E$ iff $d(v,v')\le2$, where $d$ denotes the euclidian distance. $G_V$ is the unit-disk-graph associated to $V$. Unit-disk-graphs and planar graphs are two distincts classes of graphs but the following statement presents a suffisent condition for a unit-disk-graph to be planar.

If for all $v,v'\in V$ we have $d(v,v')>\sqrt{2}$, then $G_V$ is planar.

$\bullet$ My question is : i.e. Is this value tight ? Is it possible to find a set $V\subseteq\mathbb{R}^2$ such that $\forall v,v'\in V, d(v,v')\ge \sqrt{2}$ and $G_V$ is not planar ? And if the answer is positive, what is the smallest counter-example ?

$\endgroup$
  • $\begingroup$ I suggest trying some arrangements of $K_5$ or $K_{3,3}$. $\endgroup$ – j_random_hacker May 18 '18 at 20:20
  • $\begingroup$ Please confirm that the claim is about planarity, and not the closely related concept of a planar embedding. It's quite easy to show an example of 4 points in the plane such that their pairwise distances are all $\le \sqrt 2$, with at least one distance exactly $\sqrt 2$ (implying tightness), such that two edges cross -- but the underlying abstract graph is nevertheless still planar, since it could be embedded into the plane in a different way without crossings. $\endgroup$ – j_random_hacker May 22 '18 at 9:07
  • $\begingroup$ Yes i'm interested in the abstract structure of the graph. For the moment, the smallest non-planar graph i've found has 8 vertices, I conjecture that this is the smallest one, but I cannot prove this $\endgroup$ – Mathieu Mari May 22 '18 at 13:36
  • $\begingroup$ Thanks. I have in mind a slightly tricky brute-force algorithm that could test whether any given graph is tight (that is, both (a) a unit disk graph and (b) not embeddable in the plane unless some distance is exactly $\sqrt 2$); if it is possible to find a finite set of "minimal" (frantic handwaving here) non-planar graphs, then each of them could be tested and the definitive answer found. I had thought testing $K_5$ and $K_{3,3}$ would suffice, but now realise that (without further insight) we would need to test the infinitely many graphs having either of these as a minor. $\endgroup$ – j_random_hacker May 22 '18 at 14:31
  • $\begingroup$ Sorry, in the previous comment please replace "unless some distance is exactly $\sqrt 2$" with "unless all distances are $\ge \sqrt 2$ and at least one is exactly $\sqrt 2$". To give an example of the kind of "minimality" I'm looking for, it's clear that we don't have to test graphs consisting of more than one connected component (since if such a graph is tight, then it must be because one of its components is tight). More careful inspection might yield further rules that eliminate some classes of graphs from needing to be examined, until hopefully only a finite number remain. $\endgroup$ – j_random_hacker May 22 '18 at 16:10

Your Answer

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

Browse other questions tagged or ask your own question.