Graph drawing using tabu search coupled with path relinking.

Area of Science:

• Computer Science
• Artificial Intelligence
• Graph Theory

Background:

• Graph drawing is a complex problem with various search-based optimization methods.
• Existing methods often rely on weighted sums of multiple criteria for objective functions.
• Previous research has not extensively explored tabu search and path relinking for general multi-criteria graph drawing.

Purpose of the Study:

• To propose and evaluate a novel neighborhood search method for graph drawing.
• To optimize general graph layouts with undirected straight lines using multi-criteria objective functions.
• To compare the proposed method against hill climbing and simulated annealing.

Main Methods:

• A new neighborhood search method combining tabu search and path relinking.
• Tabu search utilizes a memory list to avoid revisiting solutions.
• Path relinking generates new solutions by exploring paths between high-quality solutions, integrated periodically into the tabu search.

Main Results:

• The proposed method produced superior graph layouts compared to hill climbing and simulated annealing.
• The new method achieved better layouts using fewer evaluated solutions, indicating improved speed.
• The approach demonstrated greater scalability, successfully laying out larger graphs than state-of-the-art methods.

Conclusions:

• The novel tabu search coupled with path relinking method is effective for multi-criteria graph drawing.
• This approach offers significant improvements in layout quality, speed, and scalability over existing techniques.
• The method's efficacy is validated on both random and real-world graph datasets.