A New Exact Algorithm for the Two-Sided Crossing Minimization Problem

DOI10.1007/978-3-540-73556-4_32MaRDI QIDQ3611983zbMATH OpenOpenAlexFDO

Authors Lanbo Zheng, Christoph Buchheim

Publication date 3 March 2009

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73556-4_32

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms
• A branch-and-cut approach to the crossing number problem
• A faster fixed parameter algorithm for two-layer crossing minimization
• An improved bound on the one-sided minimum crossing number in two-layered drawings
• A New Approach to Exact Crossing Minimization

Cited in

(9)

• scientific article; zbMATH DE number 1974113 (Why is no real title available?)
• Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization
• Connecting the dots (with minimum crossings)
• A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
• A linear edge kernel for two-layer crossing minimization
• Approximation algorithms for minimizing edge crossings in radial drawings
• A variable depth neighborhood search algorithm for the min-max arc crossing problem
• Computing hive plots: a combinatorial framework
• Parameterized analysis and crossing minimization problems

Describes a project that uses

Uses Software

• GraphBase

This page was built for publication: A New Exact Algorithm for the Two-Sided Crossing Minimization Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3611983)