3

I have a digraph graph G=(V,E) that I would like to redraw because it is currently very messy. This is a flow chart that is being visualized and since |V|>1000 and each v in V has more than 1 outgoing edge, it is very hard to trace by eye. For instance; a node on the lower left corner is connected by an edge to a node on the upper right corner. It would be better, for example, if these two nodes were placed next to each other. There are too many edges and it is a pain to trace each of them.

I have access to and can change the (x,y) coordinates of all the vertices. I would like to redraw G by maintaining it's current structure, in a way that is more human-friendly. I thought that minimizing the number of intersecting edges may be something to start with.

Is there an algorithm that can help me redraw this graph?

My question is, how do I assign (x,y) coordinates to each v in V such that it is organized better and easier to trace and read? How do I express these requirements formally? Should I go with a heuristic, if this is NP? Here is an example for a somewhat organized graph and this is something messy (although much smaller than what I'm dealing with).

Any help will be greatly appreciated. Thanks.

EDIT: I'm still looking for a to-the-point answer. I've researched into planar straight-line and orthogonal drawing methods but what I've got is lengthy research papers. What I'm seeking is an implementation, pseudo-code or at least something to get me started.

EDIT 2: I'm not trying to display the graph. The input to the algorithm shall be the graph G (composed of V and E) and the output shall be {(xi, yi) for each vi in V}

1
  • nope, not homework. just trying to automate and simplify things... – Murat Derya Özen Jul 11 '11 at 16:03
4

You want to look at graphviz.org; this is a difficult problem on which there has been a lot of research, reimplementing the wheel is not the right way to go.

Probably you'll have to get the java to write out a datafile which a tool like 'dot' can read and use for the graph layout.

2
  • Thank you Tom for the answer. Can you be a bit more specific, which part of graphviz should I look into? – Murat Derya Özen Jul 10 '11 at 15:36
  • Graphviz is designed to draw the graphs for you. Rather than write your own code, Tom is suggesting that you have graphviz draw it for you. The dot language is very simple, and the code to generate dot files shouldn't take log to write. – Richard Jul 11 '11 at 20:07
0

That messy one seems to be drawn using spline, try planar straight line algorithm instead. Indeed this is a very difficult problem and I always use GraphViz as my backend graph drawing tools, you can generate that graph you want with -Gsplines=line option.

1
  • It doesn't really matter whether the edges are drawn as straight lines or curves. I'm more interested in the positions of the nodes on the 2-D plane so that fewer edges intersect each other and the length of the edges is smaller. – Murat Derya Özen Jul 11 '11 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.