Name
Title | ||
|---|---|---|
A hybrid genetic algorithm for automatic graph drawing based on the topology-shape-metric approach. |
Abstract | ||
|---|---|---|
This paper presents a new approach for automatic graph drawing based on Genetic algorithms. The classical topology-shape-metric approach for orthogonal graph drawing keeps a fixed planar embedding obtained in its first step (planarization), using it for the next two steps (orthogonalization and compaction). However, each step is itself an NP-hard problem, and the choices made and heuristics used on previous stages have a direct impact on subsequent ones. We can, alternatively, obtain a large number of planar embeddings by varying the order of insertion of the graph's edges when constructing such embeddings. Following that, the genetic algorithm is applied to select the planar embeddings that would lead to the final best drawing, after evaluating its performance on the subsequent orthogonalization and compaction steps. We formulate the problem of finding an optimal planar embedding for the graph as a permutation-based combinatorial optimization problem. The problem is then solved with the genetic algorithm, using appropriate selection, crossover and mutation operators, which were adapted from other permutation-based optimization problems, such as scheduling problems. The results show that our approach is able to find better solutions, representing improved final graph drawings than the ones found via the classical topology-shape-metric approach. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1145/1830483.1830616 | GECCO |
Keywords | Field | DocType |
automatic graph,planar embeddings,genetic algorithm,optimal planar,orthogonal graph drawing,classical topology-shape-metric approach,hybrid genetic algorithm,np-hard problem,final graph drawing,new approach,fixed planar,np hard problem,combinatorial optimization,graph drawing,scheduling problem,optimization problem | Graph drawing,Mathematical optimization,Computer science,Planar straight-line graph,Force-directed graph drawing,Null graph,Book embedding,Graph partition,Lattice graph,Optimization problem | Conference |
Citations | PageRank | References |
2 | 0.40 | 13 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bernadete Maria de Mendonça Neta | 1 | 2 | 1.07 |
| Gustavo Henrique Diniz Araujo | 2 | 2 | 0.74 |
| Frederico Gadelha Guimarães | 3 | 85 | 9.20 |
| Renato Cardoso Mesquita | 4 | 2 | 0.74 |