Paper Info
Title
A multiobjective genetic algorithm for automatic orthogonal graph drawing
Abstract
We present a multiobjective hybrid technique for automatic orthogonal graph drawing. The new methodology combines the classical approach to automatic orthogonal graph drawings,the topology-shape-metric approach, and a multiobjective genetic algorithm based on the NSGA-II method. In the topology-shape-metric method, a fixed planar embedding is obtained in the planarization step and submitted to the orthogonalization and compaction steps, in this order. In the hybrid approach, a greater number of planar embeddings is explored by varying the order of edges insertion that forms the planar embedding in the planarization step. The problem is then formulated as a multiobjective permutationbased combinatorial optimization problem, considering the minimization of the number of crossings, the number of bends and the area of the drawing. Solutions on the estimated Pareto front represent different drawings, that can be stored and selected by the user in real-time. We illustrate a possible multicriteria decision making based on fuzzy decision. The results show that the hybrid methodology using NSGA-II is able to find good and diverse solutions, when compared to the traditional topology-shape-metric method.
Year
DOI
Venue
2011
10.1145/2001576.2001703
GECCO
Keywords
Field
DocType
hybrid methodology,nsga-ii method,multiobjective genetic algorithm,hybrid approach,fixed planar embedding,greater number,planarization step,multiobjective hybrid technique,automatic orthogonal graph drawing,classical approach,genetic algorithms,genetic algorithm,pareto front,real time,multiobjective optimization,graph drawing
Graph drawing,Graph,Mathematical optimization,Computer science,Multi-objective optimization,Minification,Planar,Artificial intelligence,Orthogonalization,Machine learning,Genetic algorithm,Chemical-mechanical planarization
Conference
Citations 
PageRank 
References 
0
0.34
10
Authors
4
Name
Order
Citations
PageRank
Bernadete Maria de Mendonça Neta121.07
Gustavo Henrique Diniz Araujo220.74
Frederico G. Guimarães320224.99
Renato Cardoso Mesquita420.74