2002-12: Mathematical Programming Formulation of Rectilinear Crossing Minimization

DIMACS TR: 2002-12

Mathematical Programming Formulation of Rectilinear Crossing Minimization

Authors: Nathaniel Dean

ABSTRACT
In a {\em rectilinear drawing} of a simple graph $G$ each vertex is mapped to a distinct point in the plane and each edge is represented by a straight-line segment with appropriate ends. The goal of rectilinear crossing minimization is to find a rectilinear drawing of $G$ with as few edge crossings as possible. A new approach to rectilinear crossing minimization is presented including a formulation of the problem as a mathematical program with a linear objective function and simple quadratic constraints. Then we size the problem for various graph families. These sizings provide a mechanism for ranking crossing number problems according to their apparent complexity.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-12.ps.gz

DIMACS Home Page