map graph
{{Short description|Intersection graph representing regions on the Euclidean plane}}
File:Map graph.svg {{math|K2,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)]]
{{multiple image
|image1=Fourcorners-us.jpg
|caption1=The 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, the map graph of squares of the chessboard. A chess king can move between any two adjacent vertices of this graph.}}
In graph theory, a branch of mathematics, a map graph is an undirected graph formed as the intersection graph of finitely many simply connected and internally disjoint regions of the Euclidean plane. The map graphs include the planar graphs, but are more general. Any number of regions can meet at a common corner (as in the Four Corners of the United States, where four states meet), and when they do the map graph will contain a clique 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
| 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, a map graph of the squares of the 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, with bipartition {{math|(U,V)}}. The square 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 is the 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 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.
Computational complexity
In 1998, Mikkel Thorup claimed that map graphs can be recognized in polynomial time.{{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
| title = Characterizing and Recognizing 4-Map Graphs| volume = 81
| issue = 5
| pages = 1818–1843
| s2cid = 254038620
}}
The maximum independent set problem has a polynomial-time approximation scheme for map graphs, and the 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 leads to many other approximation algorithms and fixed-parameter tractable 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
}}.