31 Jan
2014
31 Jan
'14
8:28 p.m.
This paper by LA Szekely http://www.cs.umd.edu/~gasarch/erdos_dist/szekely.pdf proves that a V-vertex graph drawn in the plane with line segment edges, each of length=1, has at most O(V^(4/3)) edges. I think (have not checked carefully!) his proof also is valid for graphs drawn on surface of a sphere using geodesic segment edges.
--I now checked carefully. It actually is quite amazing how Szekely gets all these cool results without using anything other than the notion of "crossing number in a plane topology" which of course works on a sphere too since they have same topology. So anyhow, as (yet another) consequence, as explained last post, we now know that: not every squarefree graph is realizable.