Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs
David Eppstein · Journal of Graph Algorithms and Applications · 2018
We show that triangle-free penny graphs have degeneracy at most two, and that both triangle-free penny graphs and squaregraphs have at most $\min\bigl(2n-\Omega(\sqrt n),2n-D-2\bigr)$ edges, where $n$ is the number of vertices and $D$ is the diameter of the graph.