Map Graph
Map graphs modify the notion of planarity to consider two graph 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 k-map graph is a map graph derived from a set of regions in which at most k regions meet at any point.
See also
Facially Complete Planar Embedding, Planar GraphExplore with Wolfram|Alpha
WolframAlpha
More things to try:
References
Brandenburg, F. J. "Characterizing and Recognizing 4-Map Graphs." Algorithmica 81, 1818-1843, 2018.Chen, Z.-A. "Approximation Algorithms for Independent Sets in Map Graphs." J. Algorithms 41, 20-40, 2001.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.-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." Util. Math. 124, 157-169, 2025. https://doi.org/10.61091/um124-10.Referenced on Wolfram|Alpha
Map GraphCite this as:
Weisstein, Eric W. "Map Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MapGraph.html