Re: Connecting graph vertices with edges that never intersect
- From: Stephen Montgomery-Smith <stephen@xxxxxxxxxxxxxxxxx>
- Date: Tue, 12 Jul 2005 02:29:26 GMT
Tony wrote:
I wonder what kind of theory exists out there, if any, that can help with this problem?
Basically you are drawing a graph and you are given a set of edges that connect graph's vertices. You want to arrange positions of the vertices and/or bend the edges in such a way that any one edge never intersects any other edge (or at best you want to minimize the number of edge intersections.)
This is a well studied area - you are testing the graph for planarity. In 1974 Hopcroft and Tarjan published an algorithm for testing planarity that that linear time in the number of vertices and edges. Older work includes Kuratowski's Theorem that gives a classification of planar graphs, although his classification is somewhat impractical for computational purposes.
If the graph is not planar, I think that finding a way to draw the graph with minimal edge crossings is difficult. This is of course of great interest to people like circuit board designers. I think that it is an NP complete problem, meaning that no-one knows if an decent algorithm exists. However, I believe that there are many heuristic algorithms that attempt to give good if not best answers.
I had a student once go through the paper by Hopcroft and Tarjan, and we found it confusing in places. However, there are quite a few books on the subject which will explain these algorithms well.
I found this using google.
http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE170.HTM .
- References:
- Prev by Date: Connecting graph vertices with edges that never intersect
- Next by Date: Re: Mathematical concepts
- Previous by thread: Connecting graph vertices with edges that never intersect
- Next by thread: Re: Connecting graph vertices with edges that never intersect
- Index(es):
Relevant Pages
|
