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).
Brandenburg, F. J. "Characterizing and Recognizing 4-Map Graphs." Algorithmica81, 1818-1843, 2018.Chen,
Z.-A. "Approximation Algorithms for Independent Sets in Map Graphs." J.
Algorithms41, 20-40, 2001.Chen, Z.; Grigni, M.; and Papadimitiou,
C. "Planarity, Revisited (Extended Abstract)." In Proc. 5th WADS,
pp. 472-473, 1997.Chen, Z.-Z.; Grigni, M.; and Papadimitriou, C. H.
"Planar Map Graphs." In Proc. 30th Annual ACM Symposium on Theory of
Computing (STOC '98), Dallas, TX, May 23-26, 1998. (Ed. J. S. Vitter). New
York: ACM, pp. 514-523, 1998. https://doi.org/10.1145/276698.276865.Chen,
Z.-Z.; Grigni, M.; and Papadimitriou, C. H. "Map Graphs." J. ACM49,
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.
-map graph is a map graph derived from
a set of regions in which at most 
regions meet at any point.
