Re:Planarity - a game with planar graphs
by eru on Tuesday March 31, 2009 @04:46AM
(#539824)
Could you give me a source or the name of the algorithm, that allows this running time?
[ Parent
| on HN ]
The Wikipedia article on planarity testing cites, for instance, this paper: 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.