Planarity - a game with planar graphs

Re:Planarity - a game with planar graphs by eru on Monday March 30, 2009 @08:13AM (#538420)

Good luck. The problem may be NP complete in general.

[ Parent | on HN ]

Re:Planarity - a game with planar graphs by shrughes on Monday March 30, 2009 @09:02AM (#538449)

Well, for the cases on planarity.net, it seems O(n) to me. Or maybe something like O(n log n)

[ Parent | on HN ]

Re:Planarity - a game with planar graphs by gjm11 on Monday March 30, 2009 @12:53PM (#538736)

It's O(n) in the general case, so certainly also for the special cases on planarity.net.

[ Parent | on HN ]

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 ]

Re:Planarity - a game with planar graphs by gjm11 on Tuesday March 31, 2009 @03:42PM (#540672)

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.

[ Parent | on HN ]

Re:Planarity - a game with planar graphs by eru on Tuesday March 31, 2009 @07:04AM (#539913)

P.S. I found a O(n) running time for planarity testing - but not embedding.

[ Parent | on HN ]