UBIGRAPH
Technologies
Below are some summaries of the technology behind UbiGraph. For more detail, see the Papers section.
OpenGL
UbiGraph's rendering engine uses OpenGL, the industry standard for portable, high performance graphics. You can find out more at http://www.opengl.org/. Vertex styles and labels are handled with GLUT, the OpenGL Utility Toolkit.
XMLRPC
XMLRPC is a protocol for remote procedure calls using the HTTP transport protocol and XML encoding of arguments and responses. Using XMLRPC, you can talk to the UbiGraph server from any language which supports it. For more information, see http://www.xmlrpc.com/.
POSIX Threads (Pthreads)
The server will use up to 8 cpus for high-performance layout and rendering.
Force-directed graph layout
Force-directed graph layout is a standard technique for finding graph layouts. Vertices are treated as point particles that repel one another, and edges are modelled as springs. UbiGraph uses the Appel/Barnes-Hut algorithm to calculate pairwise forces in O(n log n) time. The ODEs are obtained using Lagrangian mechanics and integrated using standard techniques (Euler step, Runge-Kutta, Bogacki-Shampine).
Finding symmetries
Force-directed layout is good at finding symmetries. For example, a ring of vertices will be laid out as a ring, the connectivity graph of a cube will be laid out as a cube, etc. This is because of a connection between symmetries of the graph (its automorphism group) and symmetries of the space (its isometry group). If the graph automorphism group shares a subgroup with the isometry group, there are stable layouts that reflect that symmetry (i.e., in which actions of the graph automorphism subgroup commute with actions of the isometry subgroup.)
Multilevel layout
Force directed layout works well for small graphs. However, for large graphs, force-directed layout is too slow. Hence it is common practice in graph layout to first reduce the graph to smaller (coarser) graphs which are easier to lay out. The above image shows three graphs levels: a large graph that is being laid out, and two coarser versions of it. UbiGraph simultaneously lays out all the graph levels, and couples their dynamics so that coarser layouts influence finer layouts. In addition, the projection of coarser graphs onto finer graphs is itself dynamic, so that the rotation, scaling, etc. of the coarser graph converges to a least-square fit.
Demo comparing convergence times ➠ Demo of dynamic projection ➠Dynamic Coarsening
UbiGraph maintains the coarser graphs dynamically, so that changes made to the graph are automatically reflected in the coarser versions. This is done with a novel dynamic coarsening algorithm that requires O(1) randomized time per update in bounded-degree graphs. The distortion of the distance metric from a finer to coarser graph is at most two, so that the coarser graphs approximately reflect the topology of the finer graph.
Demo of Dynamic Coarsening ➠