graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a branch of mathematics, a map graph is an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...

formed as the

intersection graph In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types o ...

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 A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...

connecting the corresponding vertices, unlike planar graphs in which the largest cliques have only four vertices.. Another example of a map graph is the

king's graph In graph theory, a king's graph is a graph that represents all legal moves of the king chess piece on a chessboard where each vertex represents a square on a chessboard and each edge is a legal move. More specifically, an n \times m 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 be a planar bipartite graph, with bipartition . The

square In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90- degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length a ...

of 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 . The half-square or bipartite half is the

induced subgraph In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Defini ...

of one side of the bipartition (say ) in the square graph: its vertex set is and it has an edge between each two vertices in that are two steps apart in . The half-square is a map graph. It can be represented geometrically by finding a planar embedding of , and expanding each vertex of and its adjacent edges into a star-shaped region, so that these regions touch at the vertices of . 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. 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. The

maximum independent set In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set S of vertices such that for every two vertices in S, there is no edge connecting the tw ...

problem has a

polynomial-time approximation scheme In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems). A PTAS is an algorithm which takes an insta ...

for map graphs, and the

chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...

can be approximated to within a factor of two in polynomial time. The theory of

bidimensionality Bidimensionality theory characterizes a broad range of graph problems (bidimensional) that admit efficient approximate, fixed-parameter or kernel solutions in a broad range of graphs. These graph classes include planar graphs, map graphs, bounded ...

leads to many other approximation algorithms and

fixed-parameter tractable In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...

algorithms for optimization problems on map graphs..

Variations and related concepts

A -map graph is a map graph derived from a set of regions in which at most regions meet at any point. Equivalently, it is the half-square of a planar bipartite graph in which the vertex set (the side of the bipartition not used to induce the half-square) has maximum

degree Degree may refer to: As a unit of measurement * Degree (angle), a unit of angle measurement ** Degree of geographical latitude ** Degree of geographical longitude * Degree symbol (°), a notation used in science, engineering, and mathematics ...

. 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 In topological graph theory, a 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge. If a 1-planar graph, one of the most natural ...

, 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.

References

{{reflist Planar graphs Graph families