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.; 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. 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.
