Map graph

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.

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) in the square graph: 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] In 1998, Mikkel Thorup claimed that map graphs can be recognized in polynomial time.

[2] 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.