Chapter 20
2D Planar Maps

Ester Ezra, Eyal Flato, Efi Fogel, Dan Halperin, Iddo Hanniel, Sariel Har-Peled, Shai Hirsch, Oren Nechushtan, and Ron Wein


Planar maps are embeddings of topological maps into the plane. A planar map subdivides the plane into vertices, edges, and faces. The vertices, edges, and faces of a subdivision are the embeddings of their topological map counterparts into the plane, such that (1) each vertex is embedded as a planar point, (2) each edge is embedded as a bounded x-monotone curve, and does not contain vertices in its interior, and (3) each face is a maximal connected region of the plane that does not contain edges and vertices in its interior.