# Drawing planar graphs with integer edge lengths

It is well known that every planar graph has an embedding such that every edge is drawn as a straight line segment (Fáry's Theorem). Kemnitz and Harborth made the following stronger conjecture

Conjecture 1. Every planar graph has a straight line embedding with integer edge lengths.

I was wondering if it is possible to attack this problem with the following approach.

Conjecture 2. Let $X:=\{ x_1, \dots, x_n \}$ be a finite set of points in the plane such that no three points of $X$ are colinear. For any $\epsilon >0$, there exists $X':=\{x_1', \dots, x_n'\}$ such that for all $i, j \in [n]$

1. $d(x_i, x_i') < \epsilon$,
2. $d(x_i', x_j') \in \mathbb{Q}$, and
3. no three points of $X'$ are colinear.

To prove Conjecture 2, it suffices to prove the following conjecture.

Conjecture 3. Let $X:=\{ x_1, \dots, x_n \}$ be a finite set of points in the plane such that no three points of $X$ are colinear and all pairwise distances are rational. Then the set of points which are at rational distance from all points in $X$ is a dense subset of the plane.

Conjecture 3 is trivial for $n=1$ and easy for $n=2$. Almering proved it for $n=3$, and I think it is open for $n>3$. Note that Conjecture 3 is (essentially) a weakening of:

Conjecture 4. There exists a dense subset of the plane with all pairwise distances rational.

This question was posed by Ulam in 1945 (see this mathoverflow question for more background). So, the reason I like Conjecture 3 is that it is still strong enough to prove Conjecture 1, but appears much weaker than Conjecture 4. Unfortunately, Conjecture 3 is beyond my limited area of expertise. Hence:

Question. What are the prospects for proving Conjecture 3? A proof or disproof would be fantastic. However, even arguments suggesting that it is true/false but say beyond current technology would be most welcome.

• This is not an argument, but as you probably know, there are point configurations in the plane that cannot be realized with rational coordinates, as well as polyhedra whose combinatorial type cannot be realized with rational coordinates. It is at least conceivable that the Kemnitz/Harborth conjecture is false. – Joseph O'Rourke Feb 2 '11 at 21:04

I think conjecture 3 is actually stronger then conjecture 4.

I prove $C_3\implies C_4$:

Pick any sequence of integers $a_n$, which contains all integers infinite times.

Pick any enumeration of all squares $s_n$ in the plane with corners at rational coordinates.

Then assuming conjecture 3, at step $n$ we can find a point with rational distances in $s_{a_n}$ which is not collinear to any previously used rationals, since there are only finitely many straight lines in our set so far.

At step $\omega$, we have $\omega$ many rationals in every square, so a dense set of all rational distances.

• Actually, you may take $a_n=n$ and this still works. – Ramiro de la Vega Mar 7 '12 at 18:12
• Nice! Unfortunately, this shows that Conjecture 3 is probably false (since Conjecture 4 is probably false), so this line of attack for proving Conjecture 1 is likely to fail. – Tony Huynh Mar 7 '12 at 19:06
• There is still hope for a different method to prove Conjecture 2, but this is probably going to be the best answer that I am likely to receive, so I accepted it. Much thanks. – Tony Huynh Mar 9 '12 at 6:39

1. The Kemnitz/Harborth conjecture was proved for cubic planar graphs in:

Straight line embeddings of cubic planar graphs with integer edge lengths Jim Geelen1, Anjie Guo2,†, David McKinnon3 (Journal of Graph Theory, 2008)

They state a condition which would imply Kemnitz/Harborth (property 3.1 in their paper).

They cite the following theorem, which is related to, but not the same as, what you conjecture:

Theorem 2.1 (Berry 1992, Acta Arith). If $A, B, C \in \mathbb{R}^2$ are non-collinear points such that $dist(A, B), dist(A, C)^2,$ and $dist(B, C)^2$ are rational, then the set of points that are a rational distance from each of $A, B, C$ forms a dense subset of $\mathbb{R}^2.$

Problem D19 on pages 283-287 of Guy, Unsolved Problems In Number Theory, asks, "Is there a point all of whose distances from the corners of the unit square are rational?" This suggests that even a very weak form of Conjecture 3 is wide open (or was, as of 2004).

• This is related to but not quite I am asking since the diagonals of the unit square have irrational length. I'll comment that it is known that there are no points at rational distance from all vertices of a regular unit n-gon except perhaps when n=4,6,8,12,24. – Tony Huynh Feb 2 '11 at 22:35
• I'm sorry, you're right - still, if you haven't looked at D19, I'd recommend it, as it talks about many related problems. – Gerry Myerson Feb 2 '11 at 22:37