Journal of Graph Algorithms and Applications
|Home||Issues||Aims and Scope||Instructions for Authors|
This paper has been accepted to be published in the JGAA Special issue on Selected papers from the Twenty-fifth International Symposium on Graph Drawing and Network Visualization, GD 2017. The paper will receive a volume, an issue number, and page numbers when the whole special issue will be published.
Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs
Vol. 0, no. 0, pp. 0-0, 0. 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.
Appeared on-line: March 2018.