Heuristics and meta-heuristics for 2-layer straight line crossing minimization

DOI10.1016/S0166-218X(02)00397-9zbMath1019.68080OpenAlexW2058594920MaRDI QIDQ1811085

Manuel Laguna, Rafael Martí

Publication date: 10 June 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(02)00397-9

zbMATH Keywords

GRASP implementation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

A nonmonotone GRASP, Semidefinite relaxations of ordering problems, A variable depth neighborhood search algorithm for the min-max arc crossing problem, A rearrangement of adjacency matrix based approach for solving the crossing minimization problem, Penguins Go Parallel: A Grammar of Graphics Framework for Generalized Parallel Coordinate Plots, Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization

Uses Software

• GraphBase
• Tabu search

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A probabilistic heuristic for a computationally difficult set covering problem
• A branch and bound algorithm for minimizing the number of crossing arcs in bipartite graphs
• Edge crossings in drawings of bipartite graphs
• ARC crossing minimization in hierarchical digraphs with tabu search
• A tabu search algorithm for the bipartite drawing problem
• Greedy randomized adaptive search procedures
• A tabu thresholding algorithm for arc crossing minimization in bipartite graphs
• DAG—a program that draws directed graphs
• A Greedy Randomized Adaptive Search Procedure for the Two-Partition Problem
• GRASP and Path Relinking for 2-Layer Straight Line Crossing Minimization
• Experiments on drawing 2-level hierarchical graphs
• The NP-completeness column: An ongoing guide