4 ms·
It's O(n) in the general case, so certainly also for the special cases on planarity.net.
by gjm11 18y ago
It'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.