Refine
Year of publication
- 2004 (1)
Document Type
- Doctoral Thesis (1)
Language
- English (1)
Has Fulltext
- yes (1)
Is part of the Bibliography
- no (1)
Keywords
- Graph (1)
- Graphenklasse (1)
- Graphentheorie (1)
- Graphenzeichnen (1)
- radial level panarity (1)
- track planarity (1)
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.