Map Graphs

Zhi-Zhong Chen, Michelangelo Grigni, Christos Papadimitriou

We consider a modified notion of planarity, in which two nations of a map are considered adjacent when they share any point of their boundaries (not necessarily an edge, as planari…