Skip to main content
Kent Academic Repository

A Tabu Search Based Approach for Graph Layout

Dib, Fadi, Rodgers, Peter (2014) A Tabu Search Based Approach for Graph Layout. Journal of Visual Languages and Computing, 25 (6). pp. 912-923. ISSN 1045-926X. (doi:10.1016/j.jvlc.2014.10.019) (KAR id:43502)

PDF (Extended version for JVLC Journal) Author's Accepted Manuscript
Language: English
Download this file
(PDF/2MB)
[thumbnail of Extended version for JVLC Journal]
Request a format suitable for use with assistive technology e.g. a screenreader
PDF (DMS 2014 conference Version) Author's Accepted Manuscript
Language: English
Download this file
(PDF/935kB)
[thumbnail of DMS 2014 conference Version]
Preview
Request a format suitable for use with assistive technology e.g. a screenreader
Official URL:
http://dx.doi.org/10.1016/j.jvlc.2014.10.019

Abstract

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.

Item Type: Article
DOI/Identification number: 10.1016/j.jvlc.2014.10.019
Additional information: Work first published at DMS2014. Extended for JVLC Journal
Uncontrolled keywords: Graph Drawing, Tabu Search
Subjects: Q Science > QA Mathematics (inc Computing science)
Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Peter Rodgers
Date Deposited: 20 Oct 2014 09:39 UTC
Last Modified: 09 Jan 2024 12:41 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/43502 (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.