Map graphs modify the notion of planarity to consider two faces adjacent if they share at least one point (Chen et al. 1997, Chen et al. 1998, Thorup 1998, Chen 2001, Chen et al. 2002).
Planar graph are map graphs, as are king graphs.
A 
-map graph is a map graph derived from a set of regions in which at most 
regions meet at any point.
See also
Facially Complete Planar Embedding,
Planar Graph Explore with Wolfram|Alpha
References
Brandenburg, F. J. "Characterizing and Recognizing 4-Map Graphs." Algorithmica 81, 1818-1843, 2018.Chen, Z.; Grigni, M.; and Papadimitiou, C. "Planarity, Revisited (Extended Abstract)." In Proc. 5th WADS, pp. 472-473, 1997.Chen, Z.; Grigni, M.; and Papadimitiou, C. "Planar Map Graphs." In Proc. 30th Symposium on Theory Computing, pp. 514-523, 1998.Chen, Z.-A. "Approximation Algorithms for Independent Sets in Map Graphs." J. Algorithms 41, 20-40, 2001.Chen, Z.-Z.; Grigni, M.; and Papadimitriou, C. H. "Map Graphs." J. ACM 49, 127-138, 2002.Thorup, M. "Map Graphs in Polynomial Time." Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS 1998). Palo Alto, CA, pp. 396-405, 1998.Tilley, J.; Wagon, S.; and Weisstein, E. "A Catalog of Facially Complete Graphs." 17 Sep 2024. https://arxiv.org/abs/2409.11249.Referenced on Wolfram|Alpha
Map Graph Cite this as:
Weisstein, Eric W. "Map Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MapGraph.html
