[Wikipedia says (in the article on Fáry's theorem)](http://en.wikipedia.org/wiki/F%C3%A1ry%27s_theorem),



> 
> "Heiko Harborth raised the question of whether every planar graph has a straight line representation in which all edge lengths are integers. The answer remains unknown as of 2009."
> 
> 
> 


The reference is this:



> 
> Kemnitz, Arnfried, and Heiko Harborth. "Plane integral drawings of planar graphs." *Discrete Mathematics* **236**.1 (2001): 191-195. ([Elsevier link](http://www.sciencedirect.com/science/article/pii/S0012365X00004428))
> 
> 
> 


It is known that every $n$-vertex planar graph has a planar straight-line
grid drawing on an $O(n) \times O(n)$ grid. But of course integer vertex
coordinates do not imply integer edge lengths!


The Kemnitz-Harborth article concludes with this sentence:



> 
> "It seems to be a very hard problem to prove that every pentagon
>  with sides of integral length contains an inner point with rational distances to its
>  vertices."
> 
> 
> 


Here are my questions:



> 
> **Q**. Have there been advances on this problem in the last five years?
>  Perhaps for special cases beyond cubic graphs?
>  Any progress on the specific pentagon problem identified above?
> 
> 
> 




---


**Addendum**. User *fidbc* cited two recent papers exhibiting progress:



> 
> Biedl, Therese C. "Drawing some planar graphs with integer edge-lengths." CCCG. 2011.
> 
> 
> 


She shows that planar bipartite, series-parallel graphs, graphs with
aboricity $2$, outerplanar graphs,
and—most interestingly—that every planar graph of degree at most four,
but which is not $4$-regular, has an integral embedding.



> 
> Sun, Timothy. "Drawing some $4$-regular planar graphs with integer edge lengths."
>  CCCG. 2013.
> 
> 
> 


Timothy extends Therese's work and captures various families of (but not all) $4$-regular planar graphs.


Finally, *TMA*'s mentions the four-square-corners problem,
which is described in [this MathWorld article](http://mathworld.wolfram.com/RationalDistanceProblem.html), which says,
"J.H. Conway and R. Guy found an infinite numbers of solutions to the problem of three such distances being integers."



Integral straight-line embeddings of planar graphs
Here is the collection of references I found on a recent search on this subject:


Kemnitz, Arnfried; Harborth, Heiko
Plane integral drawings of planar graphs.
Graph theory (Kazimierz Dolny, 1997). 
Discrete Math. 236 (2001), no. 1-3, 191–195. 


Geelen, Jim; Guo, Anjie; McKinnon, David
Straight line embeddings of cubic planar graphs with integer edge lengths.
J. Graph Theory 58 (2008), no. 3, 270–274. 


Biedl, Therese
Drawing some planar graphs with integer edge-lengths
CCCG 2011, <http://www.cccg.ca/proceedings/2011/papers/paper36.pdf>


Sun, Timothy
Rigidity-Theoretic Constructions of Integral Fary Embeddings
CCCG 2011, <http://www.cccg.ca/proceedings/2011/papers/paper20.pdf>


Sun, Timothy
Drawing some 4-regular planar graphs with integer edge lengths
CCCG 2013, <http://www.cccg.ca/proceedings/2013/papers/paper_47.pdf>


M. Kleber
Encounter at far point
Math. Intelligencer 1 (2008) 50–53


Benediktovich, Vladimir I.
On rational approximation of a geometric graph.
Discrete Math. 313 (2013), no. 20, 2061–2064. 


Kemnitz and Harborth conjecture that every planar graph has such a drawing. Most of the subsequent papers center around the result that such a drawing is possible for every graph that can be reduced to nothing by removal of vertices of degree ≤ 2 and replacement of vertices of degree three by an edge connecting two neighbors (or removal of the vertex if such an edge already exists). This includes graphs with max degree four that are not 4-regular, planar bipartite graphs, (2,1)-sparse planar graphs, Apollonian networks, etc. The 2013 Sun paper shows that these drawings also exist for 4-regular planar graphs that are not 4-edge-connected, and for 4-regular planar graphs that contain a diamond subgraph (a K4 minus an edge).


The version of the problem where the vertices are additionally required to have rational coordinates, was posed in 2008 by Kleber; the Geelen et al paper above proves that it is always possible for 3-regular planar graphs, and it may be the case that many of the other results above also extend to this model. Benediktovich also proves that this kind of drawing is possible for max degree four graphs that are not 4-regular, and for 3-trees, two classes of graphs already considered for the version of the problem that only considers distances.


