On the Harborth Conjecture. Part I
arXiv:2607.02535
The paper studies Harborth's conjecture on integer‑length straight‑line drawings of planar graphs and Kleber's stronger version requiring integer coordinates, reducing the problem to rational‑distance questions for small polygons and proving a rational‑distance point exists on an interior integer diagonal of any non‑degenerate quadrilateral.
Abstract
Harborth's conjecture states that every planar graph has a crossing-free straight-line drawing in which every edge has an integer length. Kleber's strengthening asks for the vertices themselves to have integer coordinates. In this series of papers, we make progress towards settling these conjectures. We reduce Kleber's conjecture to local rational-distance statements for special polygons with at most five vertices. The triangle case is known from the results of Almering and Berry. In this paper, we prove the existence of a rational-distance point on an interior integer diagonal in all the cases for non-degenerate quadrilaterals. In the upcoming papers, we focus on non-degenerate pentagons and then degenerate quadrilaterals and degenerate pentagons.