Special issue on Selected papers from the Twenty-fifth International Symposium on Graph Drawing and Network Visualization, GD 2017
Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs
Vol. 22, no. 3, pp. 483-499, 2018. Regular paper.
Abstract 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.
Submitted: October 2017.
Reviewed: January 2018.
Revised: February 2018.
Accepted: February 2018.
Final: March 2018.
Published: September 2018.
Communicated by Fabrizio Frati and Kwan-Liu Ma
article (PDF)