A map graph is a graph represented by closed regions on the sphere, each homeomorphic
to a closed disk, with pairwise disjoint interiors. Two
vertices are adjacent exactly when the corresponding
region boundaries share a point (Chen et al. 1997,
1998, Thorup 1998, Chen 2001, Chen et al. 2002).
A -map graph is a map graph derived from
a set of regions in which at most regions meet at any point. The least such is its map number; a graph
is a map graph iff its map number
is finite.
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. The least such 
is its map number; a graph
is a map graph iff its map number
is finite.
