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