
1
Planarity Testing and Embedding
Maurizio Patrignani
Roma Tre University
1.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Propert i es and Characterizat io ns of Planar Graphs . . . 2
Basic Definitions
•
Prope r t ies
•
Characterizations
1.3 Planarity Pr obl ems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Constrained Planarity
•
Deletion and Partition Problems
•
Upward Planarity
•
Outerplanarity
1.4 History of Planarity Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5 Common Algorithmic Techniques and Tools . . . . . . . . . . . 10
1.6 ...