What algorithms are good for interactive/realtime graph-drawing?

Question

What algorithms are good for interactive/realtime graph-drawing for live data and direct-manipulation?

Failing that - what libraries do you use to draw graphs?

Suggestions;

• Prefuse information-visualization toolkit
• any others?

BTW- I mean graphs in the graph-theory sense - points and lines

• any language
• by live I mean the graph should be manipulatable once on screen.

Cherenkov

Answer 1

I would recommend any library that Jeff Heer has worked on:

• D3
• Protovis
• Flare
• Prefuse

I believe all three projects are open source. Jeff Heer is pretty good at referencing papers in his code at least in the Prefuse library. Looking at the Prefuse source:

BalloonTreeLayout: The algorithm used is that of G. Melançon and I. Herman from their research paper Circular Drawings of Rooted Trees, Reports of the Centre for Mathematics and Computer Sciences, Report Number INS–9817, 1998.

ForceDirectedLayout.java: No reference mentioned, but there are lot of comments describing how it works.

FruchtermanReingoldLayout.java: references Jung. On their website I found a paper which has references to various algorithms

NodeLinkTreeLayout.java: The algorithm used is that of Christoph Buchheim, Michael Jünger, and Sebastian Leipert from their research paper Improving Walker's Algorithm to Run in Linear Time, Graph Drawing 2002. This algorithm corrects performance issues in Walker's algorithm, which generalizes Reingold and Tilford's method for tidy drawings of trees to support trees with an arbitrary number of children at any given node.

RadialTreeLayout.java: The algorithm used is that of Ka-Ping Yee, Danyel Fisher, Rachna Dhamija, and Marti Hearst in their research paper Animated Exploration of Dynamic Graphs with Radial Layout, InfoVis 2001. This algorithm computes a radial layout which factors in possible variation in sizes, and maintains both orientation and ordering constraints to facilitate smooth and understandable transitions between layout configurations.

SquarifiedTreeMapLayout: This particular algorithm is taken from Bruls, D.M., C. Huizing, and J.J. van Wijk, "Squarified Treemaps" In Data Visualization 2000, Proceedings of the Joint Eurographics and IEEE TCVG Sumposium on Visualization, 2000, pp. 33-42. Available online at http://www.win.tue.nl/~vanwijk/stm.pdf. For more information on TreeMaps in general, see http://www.cs.umd.edu/hcil/treemap-history

Stevenage

I've read source on three software projects and I rarely see citations in code! (Prefuse included, but not the other two you mentioned) – Cherenkov

I found quite a few. See my updated answer. Just look at the layout classes to find the references. – Stevenage

Answer 2

the prefuse visualization toolkit looks like a good candidate.

Prefuse supports a rich set of features for data modeling, visualization, and interaction. It provides optimized data structures for tables, graphs, and trees, a host of layout and visual encoding techniques, and support for animation, dynamic queries, integrated search, and database connectivity. Prefuse is written in Java, using the Java 2D graphics library, and is easily integrated into Java Swing applications or web applets. Prefuse is licensed under the terms of a BSD license, and can be freely used for both commercial and non-commercial purposes. (from the homepage)

Cherenkov

Answer 3

Graph drawing is a large field. Here's a link to a graph drawing research community web site. They have an annual conference specifically about graph drawing. I can also suggest reading some of Prof. David Harel's Publications - one of his research areas is graph drawing, for example this paper. This seems like a hard problem to solve in the general case. Maybe you can limit your application to some restricted subset of graphs (planar graphs is probably too restrictive). Probably simple graphs with a small set of vertices yield easier manipulation.

Kamilah

Answer 4

There are some spiffy papers associated with Graphviz. In particular:

• E.R. Gansner, E. Koutsofios, S.C. North, and K.-P. Vo (1993) "A Technique for Drawing Directed Graphs"
• S.C. North and G. Woodhull (2002) "On-line Hierarchical Graph Drawing"

Lineament

Answer 5

I use the Dot language to describe graphs. And, the Dot compiler's output includes SVG, which is in XML and can be embedded in XHTML.

http://en.wikipedia.org/wiki/DOT_language

Himelman

not interactive as such, though the 'instaviz' iphone app is interesting. – Cherenkov

Answer 6

Not sure what you are after ...

sounds like maybe you are looking to do something similar to rrdtool?

Maybe there is some info at their site that will help:

http://oss.oetiker.ch/rrdtool/

Paralyze

Answer 7

I'm new at stackflow so sorry for the late reponse. Depending on how interactive you want to get ... you may also want't to check out Flot (uses JQuery, less interactive), or processing ... more interactive.

Vday