Skip to main content

Graph drawing using tabu search coupled with path relinking

Dib, Fadi K., Rodgers, Peter (2018) Graph drawing using tabu search coupled with path relinking. PLOS ONE, 13 (5). e0197103. ISSN 1932-6203. (doi:10.1371/journal.pone.0197103)

Abstract

Graph drawing, or the automatic layout of graphs, is a challenging problem. There are several search based methods for graph drawing which are based on optimizing an objective function which is formed from a weighted sum of multiple criteria. In this paper, we propose a new neighbourhood search method which uses a tabu search coupled with path relinking to optimize such objective functions for general graph layouts with undirected straight lines. To our knowledge, before our work, neither of these methods have been previously used in general multi-criteria graph drawing. Tabu search uses a memory list to speed up searching by avoiding previously tested solutions, while the path relinking method generates new solutions by exploring paths that connect high quality solutions. We use path relinking periodically within the tabu search procedure to speed up the identification of good solutions. We have evaluated our new method against the commonly used neighbourhood search optimization techniques: hill climbing and simulated annealing. Our evaluation examines the quality of the graph layout (objective function’s value) and the speed of layout in terms of the number of evaluated solutions required to draw a graph. We also examine the relative scalability of each method. Our experimental results were applied to both random graphs and a real-world dataset. We show that our method outperforms both hill climbing and simulated annealing by producing a better layout in a lower number of evaluated solutions. In addition, we demonstrate that our method has greater scalability as it can layout larger graphs than the state-of-the-art neighbourhood search methods. Finally, we show that similar results can be produced in a real world setting by testing our method against a standard public graph dataset.

Item Type: Article
DOI/Identification number: 10.1371/journal.pone.0197103
Subjects: Q Science
Q Science > QA Mathematics (inc Computing science) > QA 75 Electronic computers. Computer science
Divisions: Faculties > Sciences > School of Computing
Depositing User: Peter Rodgers
Date Deposited: 22 Jun 2018 12:44 UTC
Last Modified: 29 May 2019 20:39 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/67399 (The current URI for this page, for reference purposes)
Rodgers, Peter: https://orcid.org/0000-0002-4100-3596
  • Depositors only (login required):

Downloads

Downloads per month over past year