Skip to main content

Improved Neighbourhood Search-Based Methods for Graph Layout

Dib, Fadi (2018) Improved Neighbourhood Search-Based Methods for Graph Layout. Doctor of Philosophy (PhD) thesis, University of Kent,. (KAR id:69286)

Language: English
Download (12MB) Preview
[thumbnail of 13Fadi Dib Thesis.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format


Graph drawing, or the automatic layout of graphs, is a challenging problem. There are several search-based methods for graph drawing that are based on optimising a fitness function which is formed from a weighted sum of multiple criteria. This thesis proposes a new neighbourhood search-based method that uses a tabu search coupled with path relinking in order to optimise such fitness functions for general graph layouts with undirected straight lines. None 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 optimisation techniques: hill climbing and simulated annealing. Our evaluation examines the quality of the graph layout (fitness function's value) and the speed of the layout in terms of the number of the evaluated solutions required to draw a graph. We also examine the relative scalability of our 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 lay out larger graphs than the state-of-the-art neighbourhood search-based 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: Thesis (Doctor of Philosophy (PhD))
Thesis advisor: Rodgers, Peter
Uncontrolled keywords: Information Visualisation, Graph Drawing, Tabu Search, Path Relinking
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
SWORD Depositor: System Moodle
Depositing User: System Moodle
Date Deposited: 27 Sep 2018 14:11 UTC
Last Modified: 16 Feb 2021 13:58 UTC
Resource URI: (The current URI for this page, for reference purposes)
  • Depositors only (login required):


Downloads per month over past year