Planare Graphen und ihre Dualgraphen auf Zylinderoberflächen

Abstract

Die Arbeit beschäftigt sich mit planaren Zeichnungen ungerichteter und gerichteter Graphen auf Zylinderoberflächen. Im ungerichteten Fall werden die Knoten auf einer Linie parallel zur Zylinderachse positioniert, während die Kanten diese Linie nicht schneiden. Es wird gezeigt, dass eine planare Zeichnung genau dann möglich ist, wenn die Kanten des Graphen in einer double-ended queue (Deque) verarbeitet werden können. Als Konsequenz ergibt sich, dass die Deque genau die planaren Graphen mit Hamiltonpfad charakterisiert. Dies erweitert die bereits bekannte Charakterisierung planarer Graphen mit Hamiltonkreis durch den Doppelstack. Im gerichteten Fall verlaufen die Kantenkurven entweder in Richtung der Zylinderachse (SUP) oder um die Achse herum (RUP). Die Arbeit charakterisiert RUP-Graphen und zeigt, dass RUP und SUP ihre Rollen tauschen, wenn man Graph und Dualgraph betrachtet. Mit Hilfe dieser Charakterisierung wird ein Erkennungs-Algorithmus für RUP-Graphen entwickelt.