# Vertices--how can you tell if they overlap? **URL:** \ **Category:** Factual Questions\ **Created:** [July 18, 2005, 6:04pm UTC](https://boards.straightdope.com/t/vertices-how-can-you-tell-if-they-overlap/313006 "2005-07-18T18:04:08Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![merrily](https://avatars.discourse-cdn.com/v4/letter/m/ac91a4/32.png) [@merrily](https://boards.straightdope.com/u/merrily)\ **Post date:** [July 18, 2005, 6:04pm UTC](https://boards.straightdope.com/t/vertices-how-can-you-tell-if-they-overlap/313006/1 "2005-07-18T18:04:08Z")
A friend sent me this link to a flash game called [planarity](http://home.cwru.edu/~jnt5/Planarity/). I’ve been trying to figure out a way to solve the figures besides trial and error. Are there math solutions to this sort of problem? ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [July 18, 2005, 6:09pm UTC](https://boards.straightdope.com/t/vertices-how-can-you-tell-if-they-overlap/313006/2 "2005-07-18T18:09:21Z")
This represents a rather famous problem known as graph planarity. There are solutions known, but nothing that’s practically usable on any large system. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [July 18, 2005, 6:37pm UTC](https://boards.straightdope.com/t/vertices-how-can-you-tell-if-they-overlap/313006/3 "2005-07-18T18:37:04Z")
A linear (in the number of edges and nodes) time algorithm was worked out by Hopcroft and Tarjan over 30 years ago. The planarity testing part is still quite nice but the embedding algorithm is a bit messy. Several people have come up with simpler forms. For lots of links, Google on: Hopcroft Tarjan planarity Note that the best known algorithms for higher [genus](http://en.wikipedia.org/wiki/Genus_(mathematics)) surfaces get more complex quickly. While polynomial for a fixed genus, the degree of the polynomial depends on the genus. There are still some open problems in Complexity Theory regarding genus and NP-Completeness. ---
**Author:** ![Yeticus\_Rex](https://avatars.discourse-cdn.com/v4/letter/y/a698b9/32.png) [@Yeticus\_Rex](https://boards.straightdope.com/u/Yeticus_Rex)\ **Post date:** [July 18, 2005, 8:25pm UTC](https://boards.straightdope.com/t/vertices-how-can-you-tell-if-they-overlap/313006/4 "2005-07-18T20:25:51Z")
By just screwing around (I’m on level 8 right now), it seems to me that the algorithm should start by finding the verticies with lowest number of connecting edges (2 is the minimum), and complete any 3 vertices with common edges first and isolate them (as triangles), then move on to 4 vertices with 3 common edges, etc. I know I’m missing alot here for an algorithm, but my method seems to work most of the time and I’m too addicted to the damn thing to follow **ftg** ’s link. ---
**Author:** ![merrily](https://avatars.discourse-cdn.com/v4/letter/m/ac91a4/32.png) [@merrily](https://boards.straightdope.com/u/merrily)\ **Post date:** [July 18, 2005, 10:02pm UTC](https://boards.straightdope.com/t/vertices-how-can-you-tell-if-they-overlap/313006/5 "2005-07-18T22:02:23Z")
Thanks, **YR** , that does help some. The only other rule I’ve found is to move anything that has all the links on the other side over to that side. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [July 18, 2005, 10:03pm UTC](https://boards.straightdope.com/t/vertices-how-can-you-tell-if-they-overlap/313006/6 "2005-07-18T22:03:57Z")
> [@ftg](#): > > A linear (in the number of edges and nodes) time algorithm was worked out by Hopcroft and Tarjan over 30 years ago. I was under the impression that planarity testing was NP-complete. Am I misremembering, or is the some restriction on that algorithm that prevents it from solving the general case? ---
**Author:** ![Jpeg\_Jones](https://avatars.discourse-cdn.com/v4/letter/j/4bbf92/32.png) [@Jpeg\_Jones](https://boards.straightdope.com/u/Jpeg_Jones)\ **Post date:** [July 18, 2005, 11:44pm UTC](https://boards.straightdope.com/t/vertices-how-can-you-tell-if-they-overlap/313006/7 "2005-07-18T23:44:54Z")
> [@Yeticus Rex](#): > > By just screwing around (I’m on level 8 right now)… Geez, level 5 took me 5 minutes. I’m not sure I’ll even make it to level 8. ---
**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\ **Post date:** [July 19, 2005, 3:28am UTC](https://boards.straightdope.com/t/vertices-how-can-you-tell-if-they-overlap/313006/8 "2005-07-19T03:28:34Z")
> [@ultrafilter](#): > > I was under the impression that planarity testing was NP-complete. Am I misremembering, or is the some restriction on that algorithm that prevents it from solving the general case? The flash application doesn’t need to do any sort of planarity testing if it’s built right. It can just first build up a random planar graph and then rearrange all the vertices to make it non planar. Building planar graphs should be at most O(n^2). ---
**Author:** ![TJdude825](https://avatars.discourse-cdn.com/v4/letter/t/dec6dc/32.png) [@TJdude825](https://boards.straightdope.com/u/TJdude825)\ **Post date:** [July 19, 2005, 7:03am UTC](https://boards.straightdope.com/t/vertices-how-can-you-tell-if-they-overlap/313006/9 "2005-07-19T07:03:23Z")
I found this game through this “[games blog](http://www.rit.edu/~jhb4598/jblog/)” and there has been a lot of discussion of tips and strategies in the [comments](http://www.rit.edu/~jhb4598/jblog/archives/000712.php3) section for this game. BTW, if you’ve been waiting a long time for it to finish figuring out whether you’ve won or not, the game designer apparently intends to streamline that algorithm somehow in the near future. ---
**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\ **Post date:** [July 19, 2005, 12:17pm UTC](https://boards.straightdope.com/t/vertices-how-can-you-tell-if-they-overlap/313006/10 "2005-07-19T12:17:28Z")
> [@ultrafilter](#): > > I was under the impression that planarity testing was NP-complete. Am I misremembering, or is the some restriction on that algorithm that prevents it from solving the general case? Planarity testing is certainly not NP. A rather crude O(n^2) algorithm would just be for every set of lines, test whether they intersect. Checking whether a graph is planar is also not NP, you just need to check for K(3,3) and K(5) subgraphs\*. Converting a non-planar graph to a planar graph may very well be NP. - A K(3,3) graph is when you have nodes A, B, C, D, E, F and links AD, AE, AF, BD, BE, BF, CD, CE, CF A K(5) graph is when you have nodes A, B, C, D, E and all nodes are linked to all other nodes. If a graph does not contain either of these subgraphs, it can be planarised. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [July 19, 2005, 12:33pm UTC](https://boards.straightdope.com/t/vertices-how-can-you-tell-if-they-overlap/313006/11 "2005-07-19T12:33:20Z")
> [@ultrafilter](#): > > I was under the impression that planarity testing was NP-complete. Am I misremembering, or is the some restriction on that algorithm that prevents it from solving the general case? Type the following into Google: Hopcroft Tarjan planarity ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [July 19, 2005, 12:42pm UTC](https://boards.straightdope.com/t/vertices-how-can-you-tell-if-they-overlap/313006/12 "2005-07-19T12:42:49Z")
> [@Shalmanese](#): > > Planarity testing is certainly not NP. A rather crude O(n^2) algorithm would just be for every set of lines, test whether they intersect. This makes no sense. > [@](#): > > Checking whether a graph is planar is also not NP, you just need to check for K(3,3) and K(5) subgraphs. It terms of charactization this is true but is it practically useless as a basis for an algorithm. It would be like using Cramer’s rule to find matrix inverses. Good Math, lousy Computer Science. > [@](#): > > Converting a non-planar graph to a planar graph may very well be NP. “Converting”? If you mean adding new nodes at edge crossings it’s trivial. If you mean finding the minimum number of edges to remove to make it planar, that’s NP-Hard. ---
**Author:** ![merrily](https://avatars.discourse-cdn.com/v4/letter/m/ac91a4/32.png) [@merrily](https://boards.straightdope.com/u/merrily)\ **Post date:** [July 19, 2005, 4:09pm UTC](https://boards.straightdope.com/t/vertices-how-can-you-tell-if-they-overlap/313006/13 "2005-07-19T16:09:49Z")
> [@TJdude825](#): > > I found this game through this “[games blog](http://www.rit.edu/~jhb4598/jblog/)” and there has been a lot of discussion of tips and strategies in the [comments](http://www.rit.edu/~jhb4598/jblog/archives/000712.php3) section for this game. > > BTW, if you’ve been waiting a long time for it to finish figuring out whether you’ve won or not, the game designer apparently intends to streamline that algorithm somehow in the near future. Thanks for the links! I will try some of the strategies in the comments. I have noticed that they are not all equally hard–sometimes I can get to 8 fairly quickly, and sometimes I can’t get past 6. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [July 19, 2005, 4:13pm UTC](https://boards.straightdope.com/t/vertices-how-can-you-tell-if-they-overlap/313006/14 "2005-07-19T16:13:25Z")
> [@ftg](#): > > Type the following into Google: > > Hopcroft Tarjan planarity Yes, I did that. It was a simple question, you know–how long could it’ve taken you to answer it? ---
**Author:** ![Yeticus\_Rex](https://avatars.discourse-cdn.com/v4/letter/y/a698b9/32.png) [@Yeticus\_Rex](https://boards.straightdope.com/u/Yeticus_Rex)\ **Post date:** [July 19, 2005, 5:44pm UTC](https://boards.straightdope.com/t/vertices-how-can-you-tell-if-they-overlap/313006/15 "2005-07-19T17:44:46Z")
> [@TJdude825](#): > > BTW, if you’ve been waiting a long time for it to finish figuring out whether you’ve won or not, the game designer apparently intends to streamline that algorithm somehow in the near future. That was becoming an issue when I finished level 9. Then I had to leave “work” for the day so I couldn’t go on… ☹ I somehow found this puzzle therapeutic, kinda like unraveling knots which I am also good at. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [July 19, 2005, 8:28pm UTC](https://boards.straightdope.com/t/vertices-how-can-you-tell-if-they-overlap/313006/16 "2005-07-19T20:28:44Z")
> [@](#): > > Planarity testing is certainly not NP. A rather crude O(n^2) algorithm would just be for every set of lines, test whether they intersect. Perhaps I’m using somewhat different definitions here, but I don’t think that intersection is a graph-theory concept. A graph is a set of connections between vertices. The puzzles presented by that Flash game are from the start and remain planar graphs. What the player is doing is just trying to find a planar representation of them, which is not the same thing. ---
**Author:** ![Capt.Ridley\_s\_Shooting\_Party](https://avatars.discourse-cdn.com/v4/letter/c/cc9497/32.png) [@Capt.Ridley\_s\_Shooting\_Party](https://boards.straightdope.com/u/Capt.Ridley_s_Shooting_Party)\ **Post date:** [July 19, 2005, 8:43pm UTC](https://boards.straightdope.com/t/vertices-how-can-you-tell-if-they-overlap/313006/17 "2005-07-19T20:43:11Z")
Yeah, but the edges are represented as lines. If we can check that each line doesn’t intersect with another, then we can show that the correct representation has been found. ---
**Author:** ![flight](https://avatars.discourse-cdn.com/v4/letter/f/bbce88/32.png) [@flight](https://boards.straightdope.com/u/flight)\ **Post date:** [July 19, 2005, 9:04pm UTC](https://boards.straightdope.com/t/vertices-how-can-you-tell-if-they-overlap/313006/18 "2005-07-19T21:04:40Z")
Finished level 14. At that point every other move has lag associated with it and my browser suggested killing the slow script a dozen or so times during the last game. At that point it is not worth continuing. ---
**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\ **Post date:** [July 20, 2005, 6:01am UTC](https://boards.straightdope.com/t/vertices-how-can-you-tell-if-they-overlap/313006/19 "2005-07-20T06:01:48Z")
Sorry, graph theory is not my specialty and I’m not familiar with the terminology. From now on, I’ll use the term planar for an abstract graph that can be drawn with no intersecting lines and planar representation for the actual drawing of a graph in XY space with no intersecting lines. > [@ftg](#): > > This makes no sense. Testing for a planar representation is an O(n^2) algorithm at worst. > [@](#): > > It terms of charactization this is true but is it practically useless as a basis for an algorithm. It would be like using Cramer’s rule to find matrix inverses. Good Math, lousy Computer Science. Yes, there are probably more efficient algorithms but this was the one I was taught in 1st year. My point is that it establishes an upper bound on complexity which is far from NP. > [@](#): > > “Converting”? If you mean adding new nodes at edge crossings it’s trivial. If you mean finding the minimum number of edges to remove to make it planar, that’s NP-Hard. I meant converting a planar graph from a non-planar representation to a planar representation, ie: What you are meant to do in that game. AFAIK, this is still an active area of research and no P algorithms have yet been found to do it consistently. There are quite a few heuristics to bring the typical case down to something reasonable but worst case is still NP AFAIK. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [July 20, 2005, 1:08pm UTC](https://boards.straightdope.com/t/vertices-how-can-you-tell-if-they-overlap/313006/20 "2005-07-20T13:08:00Z")
> [@Shalmanese](#): > > I meant converting a planar graph from a non-planar representation to a planar representation, ie: What you are meant to do in that game. AFAIK, this is still an active area of research and no P algorithms have yet been found to do it consistently. There are quite a few heuristics to bring the typical case down to something reasonable but worst case is still NP AFAIK. Please read my first post. The Hopcroft-Tarjan linear time planarity algorithm is an _extremely famous_ graph algorithm and is one of the key reasons they were awarded the Turing Award.