Just as there are lots of different graphs out there, (the number of possible graphs on n vertices shoots exponentially as n grows), there are lots of different ways of drawing out those graphs, some methods especially made for graphs with a particular structure. The drawing method that I am introducing you all to now falls under the circle-based graph layout category. That's a mouthful! Basically what it means is that you position your graph's nodes along the perimeter of a large invisible circle and then draw the edges/lines in between nodes for all of the connections that you have. Below is an example of a simple circle-based graph visualization.
The idea is simple enough, but can easily be expanded on. What I pictured above is the crudest kind of circle based visualization that you could have for a graph. Remember that the idea behind any visualization is to make something about the graph's structure clearer to see and interpret. How are we supposed to glean any information from something that looks like an arts and crafts project from grade school? The solution is to impose additional aesthetic criteria on it and see if we can design algorithms to do at least a partial cleaning of the visual mess created. To be more specific about what this "partial cleaning" entails, it means that we would like to minimize the number of edge crossings (points where edges meet in the drawing that aren't vertices.
This is an area that I have just recently begun to explore. So far I have read up on the following approaches discussed by Yehuda and Gasner (see paper reference below).
1. order the vertices about the circle's perimeter in a way that will be less akin to fostering edge crossings
2. take some of the edges that cross on the inside of the circle and have them loop around the circle's exterior instead (a.k.a. exterior routing)
3. find densely bunched groups of edges and rather than drawing all of them individually, have one edge represent all of them. This representative edge will split off into several smaller edges at its very ends so that it is clear what edges were being represented. This edge bundling saves ink and makes the structure of the graph easier to interpret. Another way to think about it is like having a cherry twizzlers rope and you pull at the ends a little bit so that at either end of your rope you have these little "danglies" hanging. The "danglies" were bunched together in the middle which serves as the representative edge in this case. Uggh....hope that that made sense. Not the most sophisticated sounding example I'm afraid. :-P
As I find out more of the specifics regarding implementation of these ideas I will discuss them in later posts. Specifically, what I am looking into right now is how to identify those edge bunches that I was just talking so much about. :-)
The impression that I've gotten so far in my readings on graph visualization is that it is a very experimental field. There are so many different things that can affect the visualization of a graph that I imagine it must be hard to prove things. When this is the case a good approach to tackling the problem is to identify several key parameters and adjust them experimentally to see what matters, what doesn't, and which of your ideas pan out. At the very least I expect that I will be doing quite of bit of experimenting in the "graph theory lab". Much safer than experimenting in the chemistry lab I will say! :-D
If you are interested in reading more about this post's topic then I recommend looking at the following paper. It goes into detailed discussion over the 3 approaches to improved circle based visualization listed earlier.
Reference: Koren Yehuda, Gasner Emden R., Improved Circular Layouts, AT&T Labs-Research, Florham Park, NJ 07932, USA
