A branch-and-bound algorithm for the crossing number of a graph
Zheng Tan · Montana State University ScholarWorks (Montana State University) · 2000
Determining the crossing number of a graph is a well-known NP-Hard problem.This thesis will present a branch-and-bound algorithm for finding the crossing number of a graph and the details required to implement it.To the author's knowledge, this is the only implemented algorithm to find the crossing number of a graph.The algorithm begins with the vertex set and adds edges by selecting every legal option for creating a crossing or not and checks if the resulting partial graph is planar.At the point at which all edges have been added or at the point where the graph cannot be drawn without a crossing, the algorithm backtracks to see whether the graph can be drawn with fewer crossings by trying other options.Nicholson's heuristic for the linear crossing number of a graph is used as an initial upper bound for the ABSTRACT Determining the crossing number of a graph is a well-known NP-Hard problem.This thesis will present a branch-and-bound algorithm for finding the crossing number of a graph and the details required to implement it.To the author's knowledge, this is the only implemented algorithm to find the crossing number of a graph.The algorithm begins with the vertex, set and adds edges by selecting every legal option for creating a crossing or not and checks if the resulting partial graph is planar.At the point at which all edges have been added or at the point where the graph cannot be drawn without a crossing, the algorithm backtracks to see whether the graph can be drawn with fewer crossings by trying other options.Nicholson's heuristic for the linear crossing number of a graph is used as an initial upper bound for the algorithm.The algorithm is shown to be effective providing that the size of the input graph is relatively small, i.e., no more than approximately 20 edges.