Planar Graphs and their Duals on Cylinder Surfaces

Planare Graphen und ihre Dualgraphen auf Zylinderoberflächen

  • In this thesis, we investigates plane drawings of undirected and directed graphs on cylinder surfaces. In the case of undirected graphs, the vertices are positioned on a line that is parallel to the cylinder’s axis and the edge curves must not intersect this line. We show that a plane drawing is possible if and only if the graph is a double-ended queue (deque) graph, i. e., the vertices of the graph can be processed according to a linear order and the edges correspond to items in the deque inserted and removed at their end vertices. A surprising consequence resulting from these observations is that the deque characterizes planar graphs with a Hamiltonian path. This result extends the known characterization of planar graphs with a Hamiltonian cycle by two stacks. By these insights, we also obtain a new characterization of queue graphs and their duals. We also consider the complexity of deciding whether a graph is a deque graph and prove that it is NP-complete. By introducing a split operation, we obtain the splittable deque and showIn this thesis, we investigates plane drawings of undirected and directed graphs on cylinder surfaces. In the case of undirected graphs, the vertices are positioned on a line that is parallel to the cylinder’s axis and the edge curves must not intersect this line. We show that a plane drawing is possible if and only if the graph is a double-ended queue (deque) graph, i. e., the vertices of the graph can be processed according to a linear order and the edges correspond to items in the deque inserted and removed at their end vertices. A surprising consequence resulting from these observations is that the deque characterizes planar graphs with a Hamiltonian path. This result extends the known characterization of planar graphs with a Hamiltonian cycle by two stacks. By these insights, we also obtain a new characterization of queue graphs and their duals. We also consider the complexity of deciding whether a graph is a deque graph and prove that it is NP-complete. By introducing a split operation, we obtain the splittable deque and show that it characterizes planarity. For the proof, we devise an algorithm that uses the splittable deque to test whether a rotation system is planar. In the case of directed graphs, we study upward plane drawings where the edge curves follow the direction of the cylinder’s axis (standing upward planarity; SUP) or they wind around the axis (rolling upward planarity; RUP). We characterize RUP graphs by means of their duals and show that RUP and SUP swap their roles when considering a graph and its dual. There is a physical interpretation underlying this characterization: A SUP graph is to its RUP dual graph as electric current passing through a conductor to the magnetic field surrounding the conductor. Whereas testing whether a graph is RUP is NP-hard in general [Bra14], for directed graphs without sources and sink, we develop a linear-time recognition algorithm that is based on our dual graph characterization of RUP graphs.show moreshow less
  • Die Arbeit beschäftigt sich mit planaren Zeichnungen ungerichteter und gerichteter Graphen auf Zylinderoberflächen. Im ungerichteten Fall werden Zeichnungen betrachtet, bei denen die Knoten auf einer Linie parallel zur Zylinderachse positioniert werden und die Kanten diese Linie nicht schneiden dürfen. Es kann gezeigt werden, dass eine planare Zeichnung genau dann möglich ist, wenn die Kanten des Graphen in einer double-ended queue (Deque) verarbeitet werden können. Ebenso lassen sich dadurch Queue, Stack und Doppelstack charakterisieren. Eine überraschende Konsequenz aus diesen Erkenntnissen ist, 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 müssen die Kantenkurven entweder in Richtung der Zylinderachse verlaufen (SUP-Graphen) oder sich um die Achse herumbewegen (RUP-Graphen). Die Arbeit charakterisiert RUP-Graphen und zeigt, dass RUP und SUP ihre Rollen tauschen, wenn manDie Arbeit beschäftigt sich mit planaren Zeichnungen ungerichteter und gerichteter Graphen auf Zylinderoberflächen. Im ungerichteten Fall werden Zeichnungen betrachtet, bei denen die Knoten auf einer Linie parallel zur Zylinderachse positioniert werden und die Kanten diese Linie nicht schneiden dürfen. Es kann gezeigt werden, dass eine planare Zeichnung genau dann möglich ist, wenn die Kanten des Graphen in einer double-ended queue (Deque) verarbeitet werden können. Ebenso lassen sich dadurch Queue, Stack und Doppelstack charakterisieren. Eine überraschende Konsequenz aus diesen Erkenntnissen ist, 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 müssen die Kantenkurven entweder in Richtung der Zylinderachse verlaufen (SUP-Graphen) oder sich um die Achse herumbewegen (RUP-Graphen). Die Arbeit charakterisiert RUP-Graphen und zeigt, dass RUP und SUP ihre Rollen tauschen, wenn man Graph und Dualgraph betrachtet. Der SUP-Graph verhält sich dabei zum RUP-Graphen wie elektrischer Strom durch einen Leiter zum induzierten Magnetfeld. Ausgehend von dieser Charakterisierung ist es möglich einen Linearzeit-Algorithmus zu entwickeln, der entscheidet ob ein gerichteter Graph ohne Quellen und Senken ein RUP-Graph ist, während der allgemeine Fall NP-hart ist [Bra14].show moreshow less

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Christopher Auer
URN:urn:nbn:de:bvb:739-opus-27430
Advisor:Franz-Josef Brandenburg
Document Type:Doctoral Thesis
Language:English
Year of Completion:2014
Date of Publication (online):2014/12/02
Publishing Institution:Universität Passau
Granting Institution:Universität Passau, Fakultät für Informatik und Mathematik
Date of final exam:2014/11/07
Release Date:2014/12/02
Tag:radiale darstellung; zyklische darstellung
cyclic drawing; cylinder; deque layout; graph drawing; radial drawing
GND Keyword:Planarer Graph; Azyklischer gerichteter Graph; Dualer Graph; Graphentheorie; Graph; Graphenzeichnen; SPQR-Baum; Warteschlange; Zylinder
Institutes:Fakultät für Informatik und Mathematik / Mitarbeiter Lehrstuhl/Einrichtung der Fakultät für Informatik und Mathematik
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
open_access (DINI-Set):open_access
Licence (German):License LogoStandardbedingung laut Einverständniserklärung