I have adjacency matrix for graph. I need to vizualize this graph without intersecting edges. Vertex in the graph can be arranged randomly. I know one solution - enumeration of all edges for intersections. If the edges intersect, then rearrange the vertex, but it's too expensive for a large number of vertexes (more than 20). Any other ideas how to check for intersecting edges?
5
votes
What you're looking for is a planar graph drawing algorithm, like implemented by boost. Of course this can only work if the graph is indeed planar, which you haven't specified.
- Niklas B.
Here's a list of libraries that do graph layouts, which includes boost as well. If you want to implement you own, here's an algorithm that does 2d graphs.
- Arun R
1 Answers
1
votes
It's really easy to visualise any graph in a 3D plane with disjoint edges.
1) Place all the vertices in any point in the 3D plane such that no three vertices are collinear and no four vertices are in same plane.
2) Traverse through the adjacency matrix and draw a line/curve to connect the vertices.
In a 2D plane it's not guaranteed for the existence of a solution. For example take the worst case scenario that there are some 10 vertices and every vertex is connected to each other.
