Einbettung und Charakterisierung von aligned bar 1-visibility Graphen und outer fan free Graphen

In dieser Arbeit werden drei verschiedene Klassen von Graphen untersucht. Die Klassen sind die bar (1;1)-visibilty Graphen, die aligned bar 1-visibility Graphen und die outer fan free Graphen. Die Klassen werden durch ihre möglichen Einbettungen charakterisiert. Die Repräsentation der bar (1; j)-visibility Graphen ist, dass jeder Knoten als horizontaler Strich und jede Kante als vertikaler Strich gezeichnet wird. Eine Kante kann einen Knoten genau einmal schneiden und ein Knoten kann j-mal geschnitten werden. Wir erweitern die Ergebnisse von Dean et. al. und geben Beispiele mit einer maximalen Dichte an für bar (1; 2)-visibility, bar (1; 3)-visibility und bar (1; 4)-visibility Graphen und geben einen maximal dünnen Graphen für die Klasse der bar (1;1) visibility Graphen an. Wir zeigen, dass die Klassen der bar (1; j)-visibility Graphen für 1 < j < 1eine unendliche Hierarchie bilden. Abschließend beweisen wir, dass das Erkennungsproblem ob ein Graph eine bar (1;1)-visibility Repräsentation hat, NP-vollständig ist. Die Klasse der aligned bar 1-visibility Graphen (AB1V ) erhält man, indem man die bar (1;1)-visibility Repräsentation um 90 Grad dreht und alle Knoten verlängert, so dass diese alle mit der y-Koordinate 0 starten. Die relative Position bzgl. der x-Koordinate wird mit der t-Ordnung beschrieben und mit der r-Ordnung die relative Position bzgl. der y-Koordinate. Wir erweitern die Erkenntnisse von Felsner und Massow für die Klasse der AB1V Graphen bzgl. ihrer maximalen Dichte, der minimale Grad eines Knotens. Wir führen die Methode Pfadaddition ein, um anhand deren Abschlusseigenschaften zu unterscheiden, ob ein Graph in einer Klasse liegt oder nicht. Diese Methode nutzen wir, um die Beziehung der Klasse der AB1V Graphen mit anderen Klassen zu untersuchen. Für die Klasse der maximalen Graphen geben wir einen dünnen Graphen und eine untere Schranke bzgl. der Dichte an. Wir geben einen Algorithmus an, welcher eine Bucheinbettung aus einer AB1V Einbettung berechnet. Für die Klassen der optimalen AB1V Graphen geben wir einen Einbettungsalgorithmus an. Wir verbessern den Erkennungsalgorithmus von Felsner und Massow, ob ein Graph mit einer gegebenen t-Ordnung eine AB1V Einbettung besitzt. Für die Klasse der distinkt strong AB1V Graphen, Graphen in der jeder Knoten ein unterschiedliche r-Ordnung hat und maximal für die r-Ordnung ist, geben wir einen Algorithmus an, der in O(n6) eine mögliche Einbettung berechnet. Zum Schluss zeigen wir für diese Klasse, dass es exponentiell viele verschiedene Einbettungen gibt. Ein Graph hat eine outer fan free Einbettung, wenn alle Knoten inzident zu einer Fläche sind und keine Kante von zwei Kanten geschnitten wird, die adjazent zu einem Knoten sind. Wir untersuchen diese Klasse zuerst auf die Dichte. Weiter erforschen wir die Beziehung zwischen den Klassen der AB1V , RAC und k-planaren Graphen. Abschließend geben wir eine Reduktion von NAE-3-SAT auf das Erkennungsproblem von outer fan free Graphen an.

Level thesis:degree_level

thesis.doctoral

Grantor dc:publisher

Universität Passau

Year

2024

Author dc:creator

• Neuwirth, Daniel

Contributors dc:contributor

• Rutter, Ignaz
• Brandenburg, Franz J.

• Graph Drawing

Statement dc:rights

• Creative Commons - CC BY - Namensnennung 4.0 International

Repository record source_url

https://opus4.kobv.de/opus4-uni-passau/frontdoor/index/index/docId/1993

OAI identifier oai:identifier

oai:kobv.de-opus4-uni-passau:1993