Planar maps are fundamental structures in computational geometry. They are used to represent the sub- division of the plane into regions and have numerous applications. We describe the planar map package of CGAL—the Computational Geometry Algorithms Library. We discuss problems that arose in the design and implementation of the package and report the solutions we have found for them. In particular we introduce the two main classes of the design–planar maps and topological maps that enable the convenient separation between geometry and topology. We also describe the geometric traits which make our package flexible by enabling to use it with any family of curves as long as the user supplies a small set of operations for the family. Finally, we present the algorithms we implemented for point location in the map, together with experimental results that compare their performance.