Harborth's conjecture (integral straight-line drawings)

Status partial high confidence

Harborth's conjecture — that every simple planar graph has a straight-line planar embedding with all edges of integer length — remains open as of early 2025. The conjecture has been established for several special classes: cubic (3-regular) planar graphs (Geelen, Guo & McKinnon 2008; the stronger integer-coordinate form), some 4-regular planar graphs (Sun 2013), planar 3-trees and maximum-degree-4 graphs (Benediktovich 2013), and additional classes via rigidity-theory constructions (Biedl 2011, Sun 2011). Wikipedia's article on the problem, last updated February 2025, explicitly confirms the general conjecture is unsolved.

Cited literature (5)

• partial Straight line embeddings of cubic planar graphs with integer edge lengths (2008)
  Geelen, J., Guo, A., McKinnon, D. · Journal of Graph Theory, 58(3): 270–274

  Proves Harborth's conjecture (as a consequence of the stronger integer-coordinate form) for all cubic (3-regular) planar graphs.

• partial Drawing some planar graphs with integer edge-lengths (2011)
  Biedl, T. · Proceedings of the Canadian Conference on Computational Geometry (CCCG 2011)

  Proves the conjecture for additional special classes of planar graphs using direct constructions.

• partial Rigidity-Theoretic Constructions of Integral Fary Embeddings (2011)
  Sun, T. · Proceedings of the Canadian Conference on Computational Geometry (CCCG 2011)

  Constructs integral Fáry embeddings for additional planar graph classes using rigidity theory.

• partial Drawing some 4-regular planar graphs with integer edge lengths (2013)
  Sun, T. · Proceedings of the Canadian Conference on Computational Geometry (CCCG 2013)

  Proves Harborth's conjecture for certain 4-regular planar graphs.

• partial On rational approximation of a geometric graph (2013)
  Benediktovich, V. · Discrete Mathematics, 313(20): 2061–2064

  Proves the conjecture for planar 3-trees and graphs of maximum degree 4.

Reviewer notes. The Wikipedia article on Harborth's conjecture (https://en.wikipedia.org/wiki/Harborth%27s_conjecture, last edited 27 February 2025) explicitly states the general conjecture remains unsolved. Partial results cover: all 3-regular planar graphs (Geelen et al. 2008, via the stronger integer-coordinate form), some 4-regular planar graphs (Sun 2013), bipartite and series-parallel planar graphs, graphs of treewidth at most 3, and additional classes via rigidity constructions. A stronger variant requiring integer vertex coordinates (not just integer edge lengths) is also open in general. The conjecture relates to the Erdős–Ulam problem on dense rational-distance sets. Individual paper URLs could not be verified due to access restrictions and arXiv rate limits; paper details sourced from the verified Wikipedia article.

Auto-reviewed 2026-09-10 with claude-sonnet-4-6 (web search enabled).