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 '' v ...

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

of finitely many simply connected and internally disjoint regions of the

Euclidean plane In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions ...

. The map graphs include the

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...

s, but are more general. Any number of regions can meet at a common corner (as in the

Four Corners The Four Corners is a region of the Southwestern United States consisting of the southwestern corner of Colorado, southeastern corner of Utah, northeastern corner of Arizona, and northwestern corner of New Mexico. The Four Corners area ...

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

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, a map graph of the squares of the

chessboard A chessboard is a used to play chess. It consists of 64 squares, 8 rows by 8 columns, on which the chess pieces are placed. It is square in shape and uses two colours of squares, one light and one dark, in a chequered pattern. During play, the bo ...

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 In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V ar ...

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

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 Mikkel Thorup (born 1965) is a Danish computer scientist working at University of Copenhagen. He completed his undergraduate education at Technical University of Denmark and his doctoral studies at Oxford University in 1993. From 1993 to 199 ...

claimed that map graphs can be recognized in

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

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

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

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

can be approximated to within a factor of two in polynomial time. The theory of bidimensionality 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. ...

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

. A 3-map graph is a

, 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