Computing crossing numbers [Elektronische Ressource] / von Markus Chimani

Computing Crossing NumbersDissertationzur Erlangung des Grades einesDoktors der Naturwissenschaftender Technischen Universitat Dortmundan der Fakultat fur InformatikvonMarkus ChimaniDortmund2008Tag der mundlic hen Prufu ng:24.11.2008Dekan:Prof. Dr. Peter BuchholzGutachter:Prof. Dr. Petra Mutzel, Technische Universit at Dortmund Dr. Martin Skutella, Technische Universit at BerliniAbstractThe graph theoretic problem of crossing numbers has been around for over60 years, but still very little is known about this simple, yet intricate non-planarity measure. The question is easy to state: Given a graph, draw itin the plane with the minimum number of edge crossings. A lot of researchhas been devoted to giving an answer to this question, not only by graphtheoreticians, but also by computer scientists. The crossing number is centralto areas like chip design and automatic graph drawing. While there arealgorithms to solve the problem heuristically, we know that it is in generalNP-complete. Furthermore, we do not know if the problem is e cientlyapproximable, except for some special cases.In this thesis, we tackle the problem using Mathematical Programming.We show how to formulate the crossing number problem as systems of linearinequalities, and discuss how to solve these formulations for reasonably sizedgraphs to provable optimality in acceptable time|despite its theoretical com-plexity class.