A branch and bound algorithm for minimizing the number of crossing arcs in bipartite graphs

DOI10.1016/0377-2217(95)00356-8zbMath0916.90264MaRDI QIDQ1266546

Vicente Valls, Pilar Lino, Rafael Martí

Publication date: 7 October 1998

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(95)00356-8

zbMATH Keywords

branch-and-bound; bipartite graphs; acyclic directed graphs; automatic graph drawing; crossing arcs minimization

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

Related Items

Incremental bipartite drawing problem, A rearrangement of adjacency matrix based approach for solving the crossing minimization problem, 2-layer right angle crossing drawings, Crossing minimization in extended level drawings of graphs, ARC crossing minimization in hierarchical digraphs with tabu search, A tabu search algorithm for the bipartite drawing problem, Heuristics and meta-heuristics for 2-layer straight line crossing minimization, Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization

Cites Work

• Unnamed Item
• Unnamed Item
• Algorithms for drawing graphs: An annotated bibliography
• Hierarchies and planarity theory
• The NP-completeness column: An ongoing gulde
• Crossing Theory and Hierarchy Mapping
• Experiments on drawing 2-level hierarchical graphs