Map 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 (graph theory), clique 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 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 Graph power, square of is another graph on the same vertex set ...
[...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]