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
Planar Graph
Explore with Wolfram|Alpha
References
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 STOC., 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.Brandenburg, F. J.
"Characterizing and Recognizing 4-Map Graphs." Algorithmica 81,
1818-1843, 2018.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.
Cite this as:
Weisstein, Eric W. "Map Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MapGraph.html
