Mathematical Programs for Drawing Nonplanar Graphs in the Plane

摘要

Many approaches to drawing graphs in the plane can be formulated and solved as mathematical programming problems. Here, we consider only drawings of a graph where each edge is drawn as a straight-line segment, and we wish to minimize the number of edge crossings over all such drawings. Some formulations of this problem are presented that lead very naturally to other unsolved problems, some solutions, and some new open problems associated with drawing nonplanar graphs in the plane.