[Gfx-cafe] GFX Cafe Seminar Friday Oct 10, 2008

GFX Café Seminar Friday October 10, 2008
12noon - 1:15pm, ECE 237 **note change of room**

Food will be served

TITLE:
Improved Force-directed Graph Drawing in 3D for Large Graphs
by Takeshi Hakamata, UNM HPC

ABSTRACT:
Graph drawing is a way to layout a graph nicely in two or three
dimensions. Among many kinds of graph drawing techniques,
force-directed algorithms have drawn huge attention for research because
of its simplicity and quality of final layouts. The most popular model
of the force-directed algorithm is a spring-mass system supplemented by
global repulsive forces. However, the inherent O(n^2) pairwise
calculation to obtain global repulsive forces is the bottleneck and the
weakness of the algorithm, therefore many improvements have been
proposed.

This talk will present an improved force-directed drawing for large
undirected graphs in 3D using a potential-field-based approximation
algorithm to calculate global repulsive forces in linear time. Given a
graph G=(V,E) with a vertex set V and an edge set E, the repulsive force
calculation can be done in sub-linear time for |V|>10^4. This allows us
to develop a practical 3D force-directed drawing algorithm for large
graphs. Empirical results show that our implementation is faster than
other known 2D-based force-directed algorithms.

BIO:
Takeshi Hakamata is a PhD candidate in Visualization Laboratory at the
UNM Center for High Performance Computing. He received a B.S. in
Information Science from Tokyo Denki University and a M.S. in Computer
Science from the University of New Mexico. He also worked at SGI Japan
for four years.

LOCATION:
The ECE building is located on the campus of the University of
New Mexico (building 46 on the campus map). Directions can be found
here: http://www.ece.unm.edu/visitors/parking.htm

--
Pradeep Sen
Assistant Professor
Advanced Graphics Lab
Dept. of Electrical & Computer Engineering
University of New Mexico

_______________________________________________
gfx-cafe mailing list
gfx-cafe@lists.eece.unm.edu
http://lists.eece.unm.edu/mailman/listinfo/gfx-cafe