Map Graphs
<|reference_start|>Map Graphs: 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.<|reference_end|>
@article{chen1999map,
    title={Map Graphs},
    author={Zhi-Zhong Chen, Michelangelo Grigni, Christos Papadimitriou},
    journal={arXiv preprint arXiv:cs/9910013},
    year={1999},
    archivePrefix={arXiv},
    eprint={cs/9910013},
    primaryClass={cs.DM cs.DS}
}