1. I accept that I am under the control of a higher power (Muppet).

heh.  this is fun.

http://www.planarity.net/#
Permalink Send private email worldsSmallestViolin 
March 22nd, 2007 1:16am
that is fun. brought me back to my college days when I spent a good portion of junior fall semester writing a program to do just that. well, the human made the graphs and the computer's job was to solve it, and it was in 3d not 2d, but that's ok.

oh, i gave up at level 11. it was getting crowded.
Permalink Send private email strawberry snowflake 
March 22nd, 2007 10:19am
Fascinating.

The Tom DeMarco / Yourdon "Structured Analysis" approach developed software systems as a "sea of interconnected bubbles" -- this game would have been a wonderful way of 'untwisting' that sea of bubbles.
Permalink SaveTheHubble 
March 22nd, 2007 10:24am
neat. the maths must be cool.

are solutions unique? do all problems of a given number of nodes have the same level of complexity/difficulty?

I guess the algorithm to solve is iterative, and involves finding the "outer ring" path for a given subset?
Permalink $-- 
March 22nd, 2007 12:21pm
> do all problems of a given number of nodes have the same level of complexity/difficulty?

What does that mean? There are lots of non-planar graphs (see K5 and K(3,3)). Over a certain fairly small node size (10? 12?) most graphs aren't. Hence there's no solution.

http://en.wikipedia.org/wiki/Planar_graph

In this case the computer generates planar graphs which is why it's not that hard to solve them (the main issue for humans becomes making enough space on the screen to move nodes around).
Permalink Send private email strawberry snowflake 
March 22nd, 2007 12:39pm
Arrgghhhh. It's the MS Access Relationships diagram.

You are in a twisty maze of little tables.
There is a misplaced link here.
>
Permalink trollop 
March 22nd, 2007 4:57pm
I guess I mean how much work is taken to solve them. As any given graph can be presented either nearly solved or as a hellish tangle, the answer is "no, problems for a graph of a certain size are not all the same level of difficulty". Obvious now ...
Permalink $-- 
March 22nd, 2007 5:01pm
It's not really that hard. The trouble is seeing thru the irrelevant connections when the middle becomes clogged.
Permalink Send private email strawberry snowflake 
March 22nd, 2007 5:17pm

This topic is archived. No further replies will be accepted.

Other topics: March, 2007 Other topics: March, 2007 Recent topics Recent topics