... finding planar embeddings of graphs by hand is your idea of fun.
Planarity (flash) is addictive though. You get a graph (a bunch of dots, some of the dots joined with lines), and have to move the dots around so that the lines don't cross.
There's a theorem that says bending the lines doesn't help - if you can do it with curved lines, you can do it with straight lines.
Some graphs can't be solved though. There's a superior (IMO) version for gnome called gPlanarity that has 'no more than 4 crossings' type levels which are harder, and not just subjectively. There are efficient algorithms to test for planarity and find embeddings, but for nonplanar graphs even determining the minimum crossing number is NP-hard.
NP, of course, is the technical term for very, because you need a technical term for everything.
0 comments:
Post a Comment