# Map graph
> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Map_graph
> Markdown URL: https://mediated.wiki/source/Map_graph.md
> Source: https://en.wikipedia.org/wiki/Map_graph
> Source revision: 1264391225
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)
{{Short description|Intersection graph representing regions on the Euclidean plane}}
[[File:Map graph.svg|thumb|upright=1.35|A map graph (top), the [cocktail party graph](/source/cocktail_party_graph) {{math|''K''2,2,2,2}}, defined by corner adjacency of eight regions in the plane (lower left), or as the half-square of a planar bipartite graph (lower right, the graph of the [rhombic dodecahedron](/source/rhombic_dodecahedron))]]
{{multiple image
|image1=Fourcorners-us.jpg
|caption1=The [Four Corners](/source/Four_Corners) of the USA. Even though these four states meet at a point, rather than sharing a boundary of nonzero length, they form adjacent vertices in the corresponding map graph.
|image2=King's graph.svg
|caption2=The [king's graph](/source/king's_graph), the map graph of squares of the chessboard. A chess king can move between any two adjacent vertices of this graph.}}
In [graph theory](/source/graph_theory), a branch of mathematics, a '''map graph''' is an [undirected graph](/source/undirected_graph) formed as the [intersection graph](/source/intersection_graph) of finitely many simply connected and internally disjoint regions of the [Euclidean plane](/source/Euclidean_plane). The map graphs include the [planar graph](/source/planar_graph)s, but are more general. Any number of regions can meet at a common corner (as in the [Four Corners](/source/Four_Corners) of the United States, where four states meet), and when they do the map graph will contain a [clique](/source/clique_(graph_theory)) connecting the corresponding vertices, unlike planar graphs in which the largest cliques have only four vertices.[{{citation
| last1 = Chen | first1 = Zhi-Zhong
| last2 = Grigni | first2 = Michelangelo
| last3 = Papadimitriou | first3 = Christos H. | author3-link = Christos Papadimitriou
| doi = 10.1145/506147.506148
| issue = 2
| journal = [Journal of the ACM](/source/Journal_of_the_ACM)
| mr = 2147819
| pages = 127–138
| title = Map graphs
| volume = 49
| year = 2002| arxiv = cs/9910013| s2cid = 2657838
}}.] Another example of a map graph is the [king's graph](/source/king's_graph), a map graph of the squares of the [chessboard](/source/chessboard) connecting pairs of squares between which the chess king can move.
==Combinatorial representation==
Map graphs can be represented combinatorially as the "half-squares of planar bipartite graphs". That is, let {{math|''G'' {{=}} (''U'',''V'',''E'')}} be a planar [bipartite graph](/source/bipartite_graph), with bipartition {{math|(''U'',''V'')}}. The [square](/source/Graph_power) of {{mvar|G}} is another graph on the same vertex set, in which two vertices are adjacent in the square when they are at most two steps apart in {{mvar|G}}. The half-square or [bipartite half](/source/bipartite_half) is the [induced subgraph](/source/induced_subgraph) of one side of the bipartition (say {{mvar|V}}) in the square graph: its vertex set is {{mvar|V}} and it has an edge between each two vertices in {{mvar|V}} that are two steps apart in {{mvar|G}}. The half-square is a map graph. It can be represented geometrically by finding a [planar embedding](/source/graph_drawing) of {{mvar|G}}, and expanding each vertex of {{mvar|V}} and its adjacent edges into a star-shaped region, so that these regions touch at the vertices of {{mvar|U}}. Conversely, every map graph can be represented as a half-square in this way.[{{citation
| last = Thorup | first = Mikkel | authorlink = Mikkel Thorup
| contribution = Map graphs in polynomial time
| doi = 10.1109/SFCS.1998.743490
| pages = 396–405
| title = Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS 1998)
| year = 1998| isbn = 978-0-8186-9172-0 | s2cid = 36845908 }}.] However, the high exponent of the algorithm that he sketched makes it impractical, and Thorup has not published the details of his method and its proof.[{{citation
| last = Brandenburg | first = Franz J.
| date = August 2018
| doi = 10.1007/s00453-018-0510-x
| journal = [Algorithmica](/source/Algorithmica)
| title = Characterizing and Recognizing 4-Map Graphs| volume = 81
| issue = 5
| pages = 1818–1843
| s2cid = 254038620
}}]
The [maximum independent set](/source/maximum_independent_set) problem has a [polynomial-time approximation scheme](/source/polynomial-time_approximation_scheme) for map graphs, and the [chromatic number](/source/chromatic_number) can be approximated to within a factor of two in polynomial time.[{{citation
| last = Chen | first = Zhi-Zhong
| doi = 10.1006/jagm.2001.1178
| issue = 1
| journal = Journal of Algorithms
| mr = 1855346
| pages = 20–40
| title = Approximation algorithms for independent sets in map graphs
| volume = 41
| year = 2001}}.] The theory of [bidimensionality](/source/bidimensionality) leads to many other approximation algorithms and [fixed-parameter tractable](/source/parameterized_complexity) algorithms for optimization problems on map graphs.[{{citation
| last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine
| last2 = Fomin | first2 = Fedor V.
| last3 = Hajiaghayi | first3 = Mohammadtaghi | author3-link = Mohammad Hajiaghayi
| last4 = Thilikos | first4 = Dimitrios M.
| doi = 10.1145/1077464.1077468
| issue = 1
| journal = ACM Transactions on Algorithms
| mr = 2163129
| pages = 33–47
| title = Fixed-parameter algorithms for {{math|(''k'',''r'')}}-center in planar graphs and map graphs
| volume = 1
| year = 2005| citeseerx = 10.1.1.113.2070 | s2cid = 2757196 }}.][{{citation
| last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine
| last2 = Hajiaghayi | first2 = Mohammadtaghi | author2-link = Mohammad Hajiaghayi
| doi = 10.1093/comjnl/bxm033
| issue = 3
| journal = The Computer Journal
| pages = 292–302
| title = The Bidimensionality Theory and Its Algorithmic Applications
| volume = 51
| year = 2007| hdl = 1721.1/33090 | hdl-access = free
}}.][{{citation
| last1 = Fomin | first1 = Fedor V.
| last2 = Lokshtanov | first2 = Daniel
| last3 = Saurabh | first3 = Saket
| contribution = Bidimensionality and geometric graphs
| doi = 10.1137/1.9781611973099.124
| mr = 3205314
| pages = 1563–1575
| title = Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012)
| year = 2012| arxiv = 1107.2221| isbn = 978-1-61197-210-8
| s2cid = 9336216
}}.]
==Variations and related concepts==
A {{mvar|k}}-map graph is a map graph derived from a set of regions in which at most {{mvar|k}} regions meet at any point. Equivalently, it is the half-square of a planar bipartite graph in which the vertex set {{mvar|U}} (the side of the bipartition not used to induce the half-square) has maximum [degree](/source/degree_(graph_theory)) {{mvar|k}}. A 3-map graph is a [planar graph](/source/planar_graph), and every planar graph can be represented as a 3-map graph. Every 4-map graph is a [1-planar graph](/source/1-planar_graph), a graph that can be drawn with at most one crossing per edge, and every optimal 1-planar graph (a graph formed from a planar quadrangulation by adding two crossing diagonals to every quadrilateral face) is a 4-map graph. However, some other 1-planar graphs are not map graphs, because (unlike map graphs) their 1-planar drawings include crossing edges that are not part of a four-vertex complete subgraph. As an example, the [utility graph](/source/utility_graph) is 1-planar, but has no four-vertex complete subgraph, so it is not a 4-map graph.