(Not an answer; just a comment.)
It is a somewhat tangled graph. Here is a representation of $G(100)$:
![SqGraph100][1]
One can see $50+50=100=10^2$ at the lower-right corner, $69+52=111=11^2$ near the upper-right corner, $70+51=121=11^2$, left midlevel, etc.
This $G(100)$ graph has diameter $5$. But $G(1000)$ has diameter $4$.