The crossing number of a graph in the plane

Date
2005-03
Authors
Winterbach, Wynand
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : University of Stellenbosch
Abstract
Heuristics for obtaining upper bounds on crossing numbers of small graphs in the plane, and a heuristic for obtaining lower bounds to the crossing numbers of large graphs in the plane are presented in this thesis. It is shown that the two-page book layout framework is effective for deriving general upper bounds, and that it may also be used to obtain exact results for the crossing numbers of graphs. The upper bound algorithm is based on the well-kown optimization heuristics of tabu search, genetic algorithms and neural networks for obtaining two-page book layouts with few resultant edge crossings. The lower bound algorithm is based on the notion of embedding a graph into another graph, and, to the best knowledge of the author, it is the first known lower bound algorithm for the corssing number of a graph. It utilizes Dijkstra's shortest paths algorithm to embed one graph into another, in such a fashion as to minimize edge and vertex congestion values. The upper bound algorithms that were developed in this thesis were applied to all non-planar complete multipartite graphs of orders 6-13. A catalogue of drawings of these graphs with low numbers of crossings is provided in the thesis. Lower bounds on the crossing numbers of these graphs were also computed, using lowerbounds that are known for a number of complete multipartite graphs, as well as the fact that lower bounds on the crossing numbers of the subgraphs of a graph G, are lower bounds on the crossing number of G. A reference implementation of the Garey-Johnson algorithm is supplied, and finally, it is shown that Szekely's algorithm for computing the independent-odd crossing number may be converted into a heuristic algorithm for deriving upper bounds on the plane crossing number of a graph. This thesis also provides a thorough survey of results known for the crossing number of a graph in the plane. The survey especially focuses on algorithmic issues that have been proposed by researchers in the field of crossing number research.
Description
Thesis (MSc (Mathematical Sciences. Applied Mathematics))--University of Stellenbosch, 2005.
Keywords
Dissertations -- Applied mathematics, Theses -- Applied mathematics, Graph algorithms
Citation