Related Work

How to draw graphs?

Fruchterman-Reingold algorithm (force-directed graph drawing):

  • Initialize vertex positions randomly
  • Basic Idea:
    • Place vertices that are neighbors (directly connected) close together (attractive force)
    • Place vertices that are not directly connected far away from each other (repulsive force)
simple_bowtie graph (n=5, m=6)
Fruchterman-Reingold layout
complex_bowtie graph (n=33, m=32)
Fruchterman-Reingold layout
Jazz graph (n=198, m=2742)
Fruchterman-Reingold layout

➡ Problem: slow drawing speed with increasing complexity of graph (lots of nodes/edges)

How to draw graphs fast?

Meyerhenke, Nöllenburg and Schulz fast multilevel graph drawing
algorithm KaDraw:

  • Can be parallelized → fast!
  • Draws graph in (x, y) coordinates that can be saved in file
  • Yields very good results

➡ Idea: draw coordinates by KaDraw in parallel and use in graph
visualization program

How to store graphs?

Sanders and Schulz Karlsruhe High Quality Partitioning KaHIP:

  • Family of graph partitioning programsˆ
  • Contains graph structure classes and convenient algorithms

➡ Idea: use (modified) KaHIP as internal graph structure