Today I read a paper titled “Map Graphs”
The abstract is:
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, and a cubic time recognition algorithm for a restricted version: given a graph, decide whether it is realized by adjacencies in a map without holes, in which at most four nations meet at any point.