A tight bound for the number of edges of matchstick graphs

Abstract

A matchstick graph is a plane graph with edges drawn as unit-distance line segments. Harborth introduced these graphs in 1981 and conjectured that the maximum number of edges for a matchstick graph on $n$ vertices is $\lfloor 3n-\sqrt{12n-3}\rfloor$. In this paper we prove this conjecture for all $n\ge 1$. The main geometric ingredient of the proof is an isoperimetric inequality related to L'Huilier's inequality.

arXiv comment12 pages, 3 figures. Minor typos corrected