4 ms·
Well, for the cases on planarity.net, it seems O(n) to me. Or maybe something like O(n log n)
by shrughes 18y ago
Well, for the cases on planarity.net, it seems O(n) to me. Or maybe something like O(n log n)
- gjm11 18y agoIt's O(n) in the general case, so certainly also for the special cases on planarity.net.
- eru 18y agoCould you give me a source or the name of the algorithm, that allows this running time?
- eru 18y agoP.S. I found a O(n) running time for planarity testing - but not embedding.
- gjm11 18y agoThe Wikipedia article on planarity testing cites, for instance, this paper: http://jgaa.info/accepted/2004/BoyerMyrvold2004.8.3.pdf http://jgaa.info/accepted/2004/BoyerMyrvold2004.8.3.pdf which describes a not-insanely-complicated algorithm that constructs planar embeddings (or proves they don't exist) in linear time.