Language
 99% | (41 ratings) |
Jose Antonio about Don:
Open mind
Josim about Don:
Thanks for acceptance, good question
Hecke about Don:
fair discussion, hard problem. good luck!- Mark about Don:
Good question about something many people notice. 
Peter about Don:
very clear question, good follow-up discussion
EUR 8.-Can you exhibit a planar drawing of a planar graph?
A graph is a collection of vertices (or nodes) V and joining edges E = V^2. A planar graph is one which can be drawn in the plane such that no two edges intersect.
I am looking for an algorithm for finding a drawing of a planar graph with no edges overlapping.
Ideally, your algorithm can be implemented as follows: a drawing of the planar graph is given to you, but one where lots of the edges may overlap. You may move the vertices one by one, with the edges attached to them also moving in a corresponding way. You must give a procedure to systematically move the vertices so that the edges do not intersect.
Alternatively, given a list of the vertices and edges, you may give a way to draw the graph from scratch.
Please note that there will be no reward for incorrect solutions.
Good luck!
Comments:
- You must be logged in to write a comment.
- Written by Hecke
on Friday, Apr 16, 2010 at 9:37:21 AMonce i spent quite some time with
http://www.planarity.net/game.php
i'll think about my intuitive approach whether it is possible to be formulated as an algorithm, or are you already happy with Georgej's reference?
cheers
Hecke - Written by Georgej on Friday, Apr 16, 2010 at 7:06:17 AMSuch an algorithm is provided in "How to draw a planar graph on a grid" by H. De Fraysseix, J. Pach and R. Pollack.
Other interesting Questions
- Consciousness: State of the Art?asked by Pascal
EUR 20.-
- EUR 23.-
Hecke -- actually, this game was the inspiration for my question ;-) I'm up to level 14 so far. Your thoughts are welcome as long as the algorithm is determinately successful (an 'intuitive' description of why this is so will suffice) as I don't have access to the paper/book Georgej describes right now.
Don