Planar Graphs with Integer Length Straight Edges

By a result of Steinitz, Wagner, or Fary, every planar graph can be drawn in the plane such that all edges are straight line segments.

**Question:** *Is it possible to draw every planar graph so that the edges are straight line segments of integer length?*

[Comments added by Dan Archdeacon: we can extend this question to nonplanar graphs by increasing the dimension of Euclidean space. In particular, is it known that every graph can be drawn in *R^3* so that every edge is a straight line segment of integer length? If not, for a given graph *G*, what is the smallest *n* so that *G* can be drawn in *R^n* with every edge a straight line segment of integer length? Note that such a drawing exists for *n = |V(G)|* (in fact, with every edge of unit length), so the parameter is well defined.]

References:

[HKMS] H. Harborth, A. Kemnitz, M. Moller, and A. Sussenbach, Ganzzahlige planare Darstellungen der platonischen Korper, *Elem. Math.* **42** (1987) 118-122.

[HK] H. Harborth and A. Kemnitz, Integral representations of graphs, in *Contemporary methods in graph theory*} (R. Bodendiek Ed.) BIVerlag (1990) 359-367.

[HM] H. Harborth and M. Moller, Minimum integral drawings of the platonic graphs, *Math. Mag.* **67** (1994) 355-358.

Submitted by: Heiko Harborth, Diskrete Mathematik, Technische Universitat Braunschweig, Pockelsstrasse 14, D-38106 Braunschweig, Germany

Send comments to *dan.archdeacon@uvm.edu*and to *h.harborth@tu-bs.de*

August, 1995