A confluent drawing
In the revisions of one of my papers, I needed an illustration of the graph shown below, which comes from an NP-completeness reduction. This is a confluent drawing: two vertices are connected by an edge whenever there is a smooth path between them. (The paths are allowed to self-intersect, so for instance all 30 outer vertices form a clique.)
I think it's a great illustration of the power of confluent graph drawing: the graph has 37 vertices, 536 edges, and an average degree of nearly 29, but despite being so dense the graph has a lot of structure and the drawing makes the structure apparent.
Comments:
2009-05-14T15:52:40Z
I guess you need for the smooth path between two adjacent vertices to not go through any other vertex?
2009-05-14T16:02:29Z
Right.
2009-05-14T17:02:35Z
Hello, I'm so attractive to this graph at the first sight. It's incredibly beautiful! Please forgive me without knowing much about graph drawing and your previous work...and allow me to quote a question of my CS friend after showing this drawing to her: it looks more like an artwork, what's the practical use of this drawing?
2009-05-14T17:14:26Z
This drawing (or rather a less symmetrically arranged and less colorful but otherwise similar drawing) was added to one of my papers, as a way to describe an NP-completeness reduction visually, after a referee complained that the text description was difficult to understand. So the use of this specific drawing is to communicate a research idea.
2009-05-15T06:42:35Z
Thanks for your reply. Though the reduction might be complicated...this visualization is enjoyable :)
2009-05-15T20:24:24Z
Reminds me of "Railway Mazes" invented by Roger Penrose, I believe. He wrote a chapter on the subject in the recently published book: A lifetime of Puzzles.
http://www.amazon.com/Lifetime-Puzzles-Collection-Gardners-Birthday/dp/1568812450/
These mazes are effectively confluent drawings with only "Start" and "Exit" nodes but you have to figure out how to get from one to the other smoothly.
Very pretty!
-George Bell
2009-05-15T20:29:37Z
Thanks for the reference. There's a variant of confluent drawing (which I'm not using here) in which the smooth paths are not allowed to travel along the same part of a curve twice (not even in opposite directions); it's still possible in polynomial time to test whether two vertices are connected in such a drawing but it's somewhat nontrivial, enough to make for an interesting puzzle. Now I'm wondering whether that's part of the difficulty in the puzzles you refer to.
2009-05-15T20:53:19Z
Roger Penrose's article contains lots of nice hand-drawn mazes which he invented (as a child, as I recall). He discusses several techniques he devised to make them harder, but I don't remember anything about traversing curves only once. There is some switching variation he discusses at the end.
It is too bad the book is rather expensive. There doesn't seem to be much (anything?) on the web on the subject.
-George
2009-05-15T20:55:36Z
There is also a closely related concept in topology: train tracks.