My blog has been moved to a new location!

You should be automatically redirected in 6 seconds. If not, visit
and update your bookmarks.

Thursday, October 09, 2008

[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

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

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

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.

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.

The ECE building is located on the campus of the University of
New Mexico (building 46 on the campus map). Directions can be found

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

gfx-cafe mailing list

No comments: