Map graph (original) (raw)
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 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.
| Property | Value |
|---|---|
| dbo:abstract | 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 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. (en) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Map_graph.svg?width=300 |
| dbo:wikiPageID | 50947627 (xsd:integer) |
| dbo:wikiPageLength | 6931 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1096494227 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Bipartite_half dbc:Graph_families dbr:Undirected_graph dbr:Degree_(graph_theory) dbr:Induced_subgraph dbr:1-planar_graph dbc:Planar_graphs dbr:Chessboard dbr:Chromatic_number dbr:Graph_power dbr:Clique_(graph_theory) dbr:Four_Corners dbr:Graph_drawing dbr:Graph_theory dbr:King's_graph dbr:Intersection_graph dbr:Bidimensionality dbr:Bipartite_graph dbr:Planar_graph dbr:Polynomial-time_approximation_scheme dbr:Polynomial_time dbr:Mikkel_Thorup dbr:Euclidean_plane dbr:Parameterized_complexity dbr:Maximum_independent_set dbr:File:Map_graph.svg |
| dbp:caption | 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. (en) 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. (en) |
| dbp:image | Fourcorners-us.jpg (en) King's graph.svg (en) |
| dbp:wikiPageUsesTemplate | dbt:= dbt:Math dbt:Multiple_image dbt:Mvar dbt:Reflist dbt:Short_description |
| dcterms:subject | dbc:Graph_families dbc:Planar_graphs |
| rdfs:comment | 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 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. (en) |
| rdfs:label | Map graph (en) |
| owl:sameAs | yago-res:Map graph wikidata:Map graph dbpedia-hu:Map graph https://global.dbpedia.org/id/2Nuwj |
| prov:wasDerivedFrom | wikipedia-en:Map_graph?oldid=1096494227&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/King's_graph.svg wiki-commons:Special:FilePath/Fourcorners-us.jpg wiki-commons:Special:FilePath/Map_graph.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Map_graph |
| is dbo:wikiPageWikiLink of | dbr:Bipartite_half dbr:1-planar_graph dbr:Graph_power dbr:King's_graph dbr:Planar_graph dbr:Map_(graph_theory) |
| is foaf:primaryTopic of | wikipedia-en:Map_graph |
