Representations of Graphs by Outside Obstacles
Alexander Koch · 2012
Graphs that are given by an outside-obstacle representation form an interesting superclass of polygon-vertex visibility graphs, which are most studied in the field of visibility problems. We first introduce ray obstacles and compare them to previously defined poylgon and segment obstacle representations (ORs). We define “graph-invariant” maps, which describe possible movements of vertices in a visibility graph, without altering adjacencies. These might be used to continuously transform an outside-OR into a ray OR. We characterize outerplanar graphs that admit a plane outside-OR as chordal outerplane graphs. For general planar graphs we give a set of necessary conditions which we conjecture to also be sufficient. Deutsche Zusammenfassung Graphen, die durch eine Ausenhindernis-Darstellung gegeben sind, sind eine interessante Uberklasse von Polygon-Knoten-Sichtbarkeitsgraphen, die im Bereich der Sichtbarkeitsprobleme bisher am starksten untersucht wurden. In der Studienarbeit werden zunachst Strahlhindernisse eingefuhrt und mit den bereits bekannten Polygonund StreckenHindernis-Darstellungen (HD) verglichen. Da ungeklart ist, ob jeder Graph mit PolygonAusenhindernis-Darstellung auch durch eine Strahl-HD dargestellt werden kann, werden ” Graph-invariante“ Abbildungen definiert, die mogliche Verschiebungen der Knoten eines Sichtbarkeitsgraphen beschreiben, bei der die Adjazenz der Knoten unverandert bleibt. Diese konnten dazu verwendet werden Ausenhindernis-Darstellungen stetig in StrahlHDen zu uberfuhren. Im zweiten Teil der Arbeit, werden Ausenhindernisdarstellungen betrachtet, die sich uberschneidungsfrei in die Ebene einbetten lassen. Fur ausenplanare Graphen die mit einer planaren Ausenhindernisdarstellung eingebettet werden konnen, wird eine Charakterisierung als chordale ausenplanare Graphen angegeben. Fur allgemeine planare Graphen werden einige notwendige Bedingungen gezeigt, von denen vermutet wird, dass sie auch hinreichend sind.