Map graph

A map graph (top), the cocktail party graph 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)

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.

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 interior-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.^[1] 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 G = (U,V,E) be a planar bipartite graph, with bipartition (U,V). The square of 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 G. The half-square or bipartite half is the induced subgraph of one side of the bipartition (say V): its vertex set is V and it has an edge between each two vertices in V that are two steps apart in G. The half-square is a map graph. It can be represented geometrically by finding a planar embedding of G, and expanding each vertex of V and its adjacent edges into a star-shaped region, so that these regions touch at the vertices of U. Conversely, every map graph can be represented as a half-square in this way.^[1]

Computational complexity

Map graphs can be recognized in polynomial time. However, the high exponent of the known polynomial time algorithm for this problem makes it impractical.^[2] 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.^[3] The theory of bidimensionality leads to many other approximation algorithms and fixed-parameter tractable algorithms for optimization problems on map graphs.^[4][5][6]

Variations and related concepts

A k-map graph is a map graph derived from a set of regions in which at most k regions meet at any point. Equivalently, it is the half-square of a planar bipartite graph in which the vertex set U (the side of the bipartition not used to induce the half-square) has maximum degree k. A 3-map graph is a planar graph, and every planar graph can be represented as a 3-map graph. Every 4-map graph is a 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) they include crossing edges that are not part of a four-vertex complete subgraph.^[1]

References

1. Chen, Zhi-Zhong; Grigni, Michelangelo; Papadimitriou, Christos H. (2002), "Map graphs", Journal of the ACM, 49 (2): 127–138, doi:10.1145/506147.506148, MR 2147819.
2. Thorup, Mikkel (1998), "Map graphs in polynomial time", Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS 1998), pp. 396–405, doi:10.1109/SFCS.1998.743490.
3. Chen, Zhi-Zhong (2001), "Approximation algorithms for independent sets in map graphs", Journal of Algorithms, 41 (1): 20–40, doi:10.1006/jagm.2001.1178, MR 1855346.
4. Demaine, Erik D.; Fomin, Fedor V.; Hajiaghayi, Mohammadtaghi; Thilikos, Dimitrios M. (2005), "Fixed-parameter algorithms for (k,r)-center in planar graphs and map graphs", ACM Transactions on Algorithms, 1 (1): 33–47, doi:10.1145/1077464.1077468, MR 2163129.
5. Demaine, Erik D.; Hajiaghayi, Mohammadtaghi (2007), "The Bidimensionality Theory and Its Algorithmic Applications", The Computer Journal, 51 (3): 292–302, doi:10.1093/comjnl/bxm033.
6. Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket (2012), "Bidimensionality and geometric graphs", Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pp. 1563–1575, doi:10.1137/1.9781611973099.124, MR 3205314.