# Integral straight-line embeddings of planar graphs

"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)

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, which says, "J.H. Conway and R. Guy found an infinite numbers of solutions to the problem of three such distances being integers."

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.

• Heiko, not Heikod. (If I could think of 5 more characters to change, I would make the edit myself.) Gerhard "Ask Me About Jacobsthal's Function" Paseman, 2014.04.21 – Gerhard Paseman Apr 21 '14 at 16:58
• Thanks — I guess I'm not subject to the same limit, as I was able to fix it. – David Eppstein Apr 22 '14 at 6:53