Planarität von Graphen - die 'vertex addition'-Methode

ISBN-13: 9783656417903 / Niemiecki / Miękka / 2013 / 44 str.

Florian Forster

Opis

Bachelorarbeit aus dem Jahr 2011 im Fachbereich Informatik - Wirtschaftsinformatik, Note: 2,7, FernUniversitat Hagen, Sprache: Deutsch, Abstract: Als planarer Graph wird derjenige Graph bezeichnet, der sich in der Ebene darstellen lasst ohne dass sich zwei Kanten des Graphen schneiden. Die ersten Uberlegungen zur Planaritat finden sich bereits bei Euler und seinem beruhmten Polyedersatz. In den letzten Jahrzehnten, insbesondere durch die Entwicklungen im Bereich der Mikrochips (VLSI), wurde die Frage nach der planaren Darstellung eines Graphen immer relevanter. Weitere Anwendungen finden sich in samtlichen Bereichen in denen Leitungen oder Transportwege (Kanten) zwischen verschiedenen Standorten bzw. Quellen und Senken (Knoten) uberschneidungsfrei in einer Ebene gezeichnet bzw. verlegt werden mussen. Zunachst stellt sich allerdings die Frage, ob fur einen gegebenen Graphen uberhaupt eine planare Darstellung existiert. In der vorliegenden Arbeit wird ein Algorithmus mit linearer Laufzeit prasentiert der pruft, ob sich ein gegebener Graph planar in der Ebene darstellen lasst.