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 planarity requires). Such adjacencies define a  map graph . We give an NP characterization for such graphs, derive some consequences regarding sparsity and coloring, and survey some algorithmic results.
['Zhi-Zhong Chen', 'Michelangelo Grigni', 'Christos H. Papadimitriou']
Map graphs