TY - THES A1 - Bachmaier, Christian T1 - Circle Planarity of Level Graphs T1 - Kreisplanarität von Level-Graphen N2 - In this dissertation we generalise the notion of level planar graphs in two directions: track planarity and radial planarity. Our main results are linear time algorithms both for the planarity test and for the computation of an embedding, and thus a drawing. Our algorithms use and generalise PQ-trees, which are a data structure for efficient planarity tests. N2 - In dieser Arbeit wird der Begriff Level-Planarität von Graphen auf zwei Arten erweitert: Spur-Planarität und radiale Level-Planarität. Die Hauptergebnisse sind Linearzeitalgorithmen zum Testen dieser Arten von Planarität und zur Erstellung einer entsprechenden Einbettung und somit einer Zeichnung. Die Algorithmen verwenden und generalisieren PQ-Bäume, eine bei effizienten Planaritätstests verwendete Datenstruktur. KW - Graphentheorie KW - Graphenklasse KW - Graphenzeichnen KW - Graph KW - radial level panarity KW - track planarity Y1 - 2004 UR - https://opus4.kobv.de/opus4-uni-passau/frontdoor/index/index/docId/34 UR - https://nbn-resolving.org/urn:nbn:de:bvb:739-opus-385 ER -