Schmidt, Jens M.Jens M.Schmidt2020-10-192020-10-192007-03-16Masterarbeit, Fachbereich Informatik der Universität Dortmund: 2007,4 (2007)http://hdl.handle.net/11420/7598Ein Graph ist nach dem Satz von Kuratowski genau dann planar, wenn er keine Kuratowski-Subdivisions enth\"alt. Eine einzelne davon kann von modernen Planarit\"atstests bei nicht planaren Eingabegraphen in Linearzeit extrahiert werden. Allerdings existieren Anwendungen, die nicht nur eine, sondern m\"oglichst viele dieser Kuratowski-Subdivisions ben\"otigen. Dazu geh\"oren Branch-and-Cut-Algorithmen f\"ur einige NP-schwere Probleme, wie beispielsweise die Kreuzungsminimierung oder auch verschiedene Varianten des Maximum Planar Subgraph Problems. Die Kuratowski-Subdivisions erm\"oglichen dort die Berechnung von zus\"atzlichen nebenbedingungen einer LP-Relaxierung. Dabei ist es w\"unschenswert, dass die Kuratowski-Subdivisions paarweise entweder m\"oglichst viele Kanten gemeinsam haben oder weitgehend kantendisjunkt sind. In dieser Diplomarbeit wird ein Algorithmus entworfen und analysiert, der mehrere Kuratowski-Subdivisions in linearer Zeit O(n + m + Sum_(K in S) |E(K)|) extrahieren kann, wobei S die Menge der gefundenen Kuratowski-Subdivisions ist. Dieser Algorithmus stellt eine Erweiterung des aktuellen Planarit\"atstests von Boyer und Myrvold dar und kann zus\"atzlich so modifiziert werden, dass entweder m\"oglichst \"ahnliche oder m\"oglichst verschiedene Kuratowski-Subdivisions ausgegeben werden. Die Laufzeit des Algorithmus ist dabei asymptotisch optimal. Aus diesem Algorithmus wird ein zweiter Ansatz entwickelt, der in der Praxis mehr Kuratowski-Subdivisions extrahieren kann, daf\"ur aber zu einer superlinearen Laufzeit f\"uhrt. Beide Verfahren werden implementiert und deren Praxistauglichkeit verglichen.deTU DortmundMathematikMaster ThesisOther