Paper Info

Title | ||
---|---|---|

Multi-level graph layout on the GPU. |

Abstract | ||
---|---|---|

This paper presents a new algorithm for force directed graph layout on the GPU. The algorithm, whose goal is to compute layouts accurately and quickly, has two contributions. The first contribution is proposing a general multi-level scheme, which is based on spectral partitioning. The second contribution is computing the layout on the GPU. Since the GPU requires a data parallel programming model, the challenge is devising a mapping of a naturally unstructured graph into a well-partitioned structured one. This is done by computing a balanced partitioning of a general graph. This algorithm provides a general multi-level scheme, which has the potential to be used not only for computation on the GPU, but also on emerging multi-core architectures. The algorithm manages to compute high quality layouts of large graphs in a fraction of the time required by existing algorithms of similar quality. An application for visualization of the topologies of ISP (Internet Service Provider) networks is presented. |

Year | DOI | Venue |
---|---|---|

2007 | 10.1109/TVCG.2007.70580 | IEEE Trans. Vis. Comput. Graph. |

Keywords | DocType | Volume |

multi-level graph layout,high quality layout,similar quality,balanced partitioning,graph layout,large graph,spectral partitioning,general graph,unstructured graph,new algorithm,general multi-level scheme,graph partitioning,internet,high performance computing,application software,network topology,indexation,computer architecture,acceleration,computational modeling,visualization,directed graph,programming model,computer graphics,quality management,layout,graph theory,parallel programming | Journal | 13 |

Issue | ISSN | Citations |

6 | 1077-2626 | 56 |

PageRank | References | Authors |

2.85 | 26 | 2 |

Authors (2 rows)

Cited by (56 rows)

References (26 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Yaniv Frishman | 1 | 127 | 6.17 |

Ayellet Tal | 2 | 3262 | 161.05 |