Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Minimize Cross Edges in a Graph

I am using networkx (a python graph-drawing package) http://networkx.lanl.gov/index.html for one of my project. Though networkx is pretty cool, the display function kind of sucks due to number of cross edges. Is there a way to minimize cross edges in a graph? I mean an algorithm which can sort the nodes in a way such that cross edges are minimized?

like image 282
Anil Katti Avatar asked Feb 20 '11 16:02

Anil Katti


People also ask

What is a cross edge in a graph?

Cross Edge: It is a edge which connects two node such that they do not have any ancestor and a descendant relationship between them.

Do undirected graphs have cross edges?

First, for an undirected graph the proof is trivial since technically speaking the edges of an undirected graph are divided into only tree and back edges. Thus, there are no cross edges in an undirected graph.

What are forward edges?

A forward edge is a non-tree edge from a vertex to one of its descendants. A cross edge is an edge from a vertex u to a vertex v such that the subtrees rooted at u and v are distinct. A back edge is an edge from a vertex to one of its ancestors.

Can BFS have back edges?

I had this same question...and the answer is that there are no cross edges in the BFS, but that the BFS tree itself encodes all the edges that would have been back-edges and forward-edges in the DFS tree as tree edges in the BFS tree, such that the remaining edges which the undirected graph has, but which are still not ...


1 Answers

Determining a planar graph layout which minimizes the number of crossings is NP-Hard. See the wiki page on Crossing Number.

You could try some heuristics, force based layout are quite popular I believe (graphviz uses them, if I recollect correctly).

You could also try some approximation algorithms, you should find references on the wiki page I linked.

Hope that helps.

like image 177
Aryabhatta Avatar answered Sep 26 '22 22:09

Aryabhatta