A Tabu Search Based Approach for Graph Layout

This paper describes an automated tabu search based method for drawing general graph layouts with straight lines. To our knowledge, this is the first time tabu methods have been applied to graph drawing. We formulated the task as a multi-criteria optimization problem with a number of

metrics which are used in a weighted fitness function to measure the aesthetic

quality of the graph layout. The main goal of this work is to speed up the graph

layout process without sacrificing layout quality. To achieve this, we use a tabu

search based method that goes through a predefined number of iterations to minimize

the value of the fitness function. Tabu search always chooses the best solution in

the neighbourhood. This may lead to cycling, so a tabu list is used to store moves

that are not permitted, meaning that the algorithm does not choose previous

solutions for a set period of time. We evaluate the method according to the time

spent to draw a graph and the quality of the drawn graphs. We give experimental

results applied on random graphs and we provide statistical evidence that our

method outperforms a fast search-based drawing method (hill climbing) in execution

time while it produces comparably good graph layouts.We also demonstrate the method

on real world graph datasets to show that we can reproduce similar results in a

real world setting.