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.eduand to h.harborth@tu-bs.de

August, 1995