what is the probability that a graph this size is planar? does that question even make sense? bob --- Dan Asimov wrote:
Well, I'd probably try it, if compute time were not at issue, just to see what the graph, if planar, looks like when embedded in the plane.
--Dan
On 2013-02-17, at 4:21 PM, Gareth McCaughan wrote:
On 17/02/2013 23:41, Dan Asimov wrote:
A quick peek at Wikipedia seems to indicate that they address only algorithms that avoid using graph drawing in the plane.
But this doesn't sound like such a bad idea: Start with any embedding of the vertices in the plane, and slide them so that the sum of squared errors between the N choose 2 graph distances, and their corresponding planar distances, decreases to a local minimum (i.e., sliding down the gradient). Then check whether any two edges in the plane intersect. If they do, repeat this with a variety of starting embeddings in the hope of reaching the absolute minimum (up to scaling, say normalized by keeping [the sum of all n choose 2 planar distances] equal to a constant. Why would one do that, rather than using one of the deterministic linear-time algorithms mentioned on the Wikipedia page?
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun