Also: the boldface I is meant to be the indicator function of the set E.

Thanks for the suggestions, I will modify my question accordingly! Yes in my situation the matrix is in fact symmetric, I will mention this.

It's an interesting question; but for the picturesque version, if the density of air particles is small enough for this approximation to be valid (for collisions to form an unimportant part of the dynamics) then the air will be too far thin for you to breathe.

Fedor, thanks for this answer! I believe that the argument in your second paragraph is close to correct, except that your probability estimate is a little too strong. A binomial event of this form will have Poisson rather than Gaussian tails (so tails of the form $exp(−c(K\log K)m) when K is somewhat large). So I think this argument can show an upper bound of $O(logn/loglogn)$.

actually, what i described gives something weaker than David's assertion but still stronger than what you asked for. it's not hard to get from what i described to david's assertion, though (but it will result in edges that are very spirally).

here is one way to see that the first assertion of David's answer is true. take any planar drawing of your graph on a sphere, and then draw a continuous simple closed curve that passes through all the vertices of your graph. now pull your curve along the surface of the sphere until it forms a great circle and at the same time stretch and smoosh the two regions the curve bounds so they become hemispheres. this will change the shape of your edges but will not change the fact that the drawing is planar. now all your vertices are on a line, which is actually more than what you asked for.