Drawing planar graphs with integer edge lengths - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T03:01:53Z http://mathoverflow.net/feeds/question/54104 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/54104/drawing-planar-graphs-with-integer-edge-lengths Drawing planar graphs with integer edge lengths Tony Huynh 2011-02-02T15:57:29Z 2012-03-07T17:50:54Z <p>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</p> <p><strong>Conjecture 1.</strong> Every planar graph has a straight line embedding with <em>integer</em> edge lengths. </p> <p>I was wondering if it is possible to attack this problem with the following approach.</p> <p><strong>Conjecture 2.</strong> 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]$</p> <ol> <li>$d(x_i, x_i') &lt; \epsilon$,</li> <li>$d(x_i', x_j') \in \mathbb{Q}$, and</li> <li>no three points of $X'$ are colinear.</li> </ol> <p>To prove Conjecture 2, it suffices to prove the following conjecture.</p> <p><strong>Conjecture 3.</strong> 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.</p> <p>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:</p> <p><strong>Conjecture 4.</strong> There exists a dense subset of the plane with all pairwise distances rational.</p> <p>This question was posed by Ulam in 1945 (see <a href="http://mathoverflow.net/questions/19127/is-there-a-dense-subset-of-the-real-plane-with-all-pairwise-distances-rational/19129#19129" rel="nofollow">this</a> 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:</p> <blockquote> <p><strong>Question.</strong> 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. </p> </blockquote> http://mathoverflow.net/questions/54104/drawing-planar-graphs-with-integer-edge-lengths/54106#54106 Answer by Igor Rivin for Drawing planar graphs with integer edge lengths Igor Rivin 2011-02-02T16:28:20Z 2011-02-02T16:43:13Z <p>Not quite an answer, but:</p> <ol> <li>The Kemnitz/Harborth conjecture was proved for cubic planar graphs in:</li> </ol> <p>Straight line embeddings of cubic planar graphs with integer edge lengths Jim Geelen1, Anjie Guo2,†, David McKinnon3 (Journal of Graph Theory, 2008)</p> <p>They state a condition which would imply Kemnitz/Harborth (property 3.1 in their paper).</p> <p>They cite the following theorem, which is related to, but not the same as, what you conjecture:</p> <p>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.$</p> http://mathoverflow.net/questions/54104/drawing-planar-graphs-with-integer-edge-lengths/54140#54140 Answer by Gerry Myerson for Drawing planar graphs with integer edge lengths Gerry Myerson 2011-02-02T22:14:45Z 2011-02-02T22:14:45Z <p>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). </p> http://mathoverflow.net/questions/54104/drawing-planar-graphs-with-integer-edge-lengths/90487#90487 Answer by Holowitz for Drawing planar graphs with integer edge lengths Holowitz 2012-03-07T17:36:55Z 2012-03-07T17:50:54Z <p>I think conjecture 3 is actually stronger then conjecture 4. </p> <p>I prove $C_3\implies C_4$:</p> <p>Pick any sequence of integers $a_n$, which contains all integers infinite times.</p> <p>Pick any enumeration of all squares $s_n$ in the plane with corners at rational coordinates.</p> <p>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.</p> <p>At step $\omega$, we have $\omega$ many rationals in every square, so a dense set of all rational distances.</p>