Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
The crossing number of a graph in the plane
Thesis (MSc (Mathematical Sciences. Applied Mathematics))--University of Stellenbosch, 2005.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
Stellenbosch : University of Stellenbosch
2008
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867614032308994048 |
|---|---|
| access_status_str | Open Access |
| author | Winterbach, Wynand |
| author2 | Van Vuuren, J. H. |
| author_browse | Van Vuuren, J. H. Winterbach, Wynand |
| author_facet | Van Vuuren, J. H. Winterbach, Wynand |
| author_sort | Winterbach, Wynand |
| collection | Thesis |
| dc_rights_str_mv | University of Stellenbosch |
| description | Thesis (MSc (Mathematical Sciences. Applied Mathematics))--University of Stellenbosch, 2005. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/2242 |
| institution | Stellenbosch University (South Africa) |
| language | English |
| last_indexed | 2026-06-10T12:45:35.384Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2008 |
| publishDateRange | 2008 |
| publishDateSort | 2008 |
| publisher | Stellenbosch : University of Stellenbosch |
| publisherStr | Stellenbosch : University of Stellenbosch |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/2242 The crossing number of a graph in the plane Winterbach, Wynand Van Vuuren, J. H. University of Stellenbosch. Faculty of Science. Dept. of Mathematical Sciences. Applied Mathematics. Dissertations -- Applied mathematics Theses -- Applied mathematics Graph algorithms Thesis (MSc (Mathematical Sciences. Applied Mathematics))--University of Stellenbosch, 2005. 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. 2008-08-11T09:18:33Z 2010-06-01T08:44:10Z 2008-08-11T09:18:33Z 2010-06-01T08:44:10Z 2005-03 Thesis http://hdl.handle.net/10019.1/2242 en University of Stellenbosch application/pdf Stellenbosch : University of Stellenbosch |
| spellingShingle | Dissertations -- Applied mathematics Theses -- Applied mathematics Graph algorithms Winterbach, Wynand The crossing number of a graph in the plane |
| title | The crossing number of a graph in the plane |
| title_full | The crossing number of a graph in the plane |
| title_fullStr | The crossing number of a graph in the plane |
| title_full_unstemmed | The crossing number of a graph in the plane |
| title_short | The crossing number of a graph in the plane |
| title_sort | crossing number of a graph in the plane |
| topic | Dissertations -- Applied mathematics Theses -- Applied mathematics Graph algorithms |
| url | http://hdl.handle.net/10019.1/2242 |
| work_keys_str_mv | AT winterbachwynand thecrossingnumberofagraphintheplane AT winterbachwynand crossingnumberofagraphintheplane |