Penny graph (original) (raw)
In geometric graph theory, a penny graph is a contact graph of unit circles. It is formed from a collection of unit circles that do not cross each other, by creating a vertex for each circle and an edge for every pair of tangent circles. The circles can be represented physically by pennies, arranged without overlapping on a flat surface, with a vertex for each penny and an edge for each two pennies that touch.
| Property | Value |
|---|---|
| dbo:abstract | In geometric graph theory, a penny graph is a contact graph of unit circles. It is formed from a collection of unit circles that do not cross each other, by creating a vertex for each circle and an edge for every pair of tangent circles. The circles can be represented physically by pennies, arranged without overlapping on a flat surface, with a vertex for each penny and an edge for each two pennies that touch. Penny graphs have also been called unit coin graphs, because they are the coin graphs formed from unit circles. If each vertex is represented by a point at the center of its circle, then two vertices will be adjacent if and only if their distance is the minimum distance among all pairs of points. Therefore, penny graphs have also been called minimum-distance graphs, smallest-distance graphs, or closest-pairs graphs. Similarly, in a mutual nearest neighbor graph that links pairs of points in the plane that are each other's nearest neighbors, each connected component is a penny graph, although edges in different components may have different lengths. Every penny graph is a unit disk graph and a matchstick graph.Like planar graphs more generally, they obey the four color theorem, but this theorem is easier to prove for penny graphs.Testing whether a graph is a penny graph, or finding its maximum independent set, is NP-hard; however, both upper and lower bounds are known for the size of the maximum independent set, higher than the bounds that are possible for arbitrary planar graphs. (en) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Penny_graph.jpg?width=300 |
| dbo:wikiPageID | 53242630 (xsd:integer) |
| dbo:wikiPageLength | 17953 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1117587950 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Degeneracy_(graph_theory) dbc:Circle_packing dbc:Geometric_graphs dbr:Paul_Erdős dbr:Penny dbr:Unit_circle dbr:Unit_distance_graph dbr:Delaunay_triangulation dbc:Planar_graphs dbr:Maximum_disjoint_set dbr:Geometric_graph_theory dbr:Nearest_neighbor_graph dbr:Graph_coloring dbr:NP-hard dbr:Contact_graph dbr:Convex_hull dbr:Closest_pair_of_points_problem dbr:Tangent_circles dbr:Tree_(graph_theory) dbr:Triangle-free_graph dbr:Triangular_tiling dbr:Floor_function dbr:Four-color_theorem dbr:Four_color_theorem dbr:Grötzsch's_theorem dbr:Intersection_graph dbr:Baker's_technique dbr:Squaregraph dbr:Planar_graph dbr:Polynomial-time_approximation_scheme dbr:Circle_packing_theorem dbr:Connected_component_(graph_theory) dbr:Matchstick_graph dbr:Unit_disk_graph dbr:Kissing_number_problem dbr:Maximum_independent_set dbr:Square_grid dbr:File:Sierpinski_Pascal_triangle.svg dbr:File:Penny_graph.jpg dbr:File:Penny_graph_11_nodes.svg dbr:File:Triangle-free_penny_graph.jpg |
| dbp:wikiPageUsesTemplate | dbt:Math dbt:Mvar dbt:R dbt:Reflist dbt:Sfnp dbt:Short_description dbt:Unsolved |
| dcterms:subject | dbc:Circle_packing dbc:Geometric_graphs dbc:Planar_graphs |
| rdfs:comment | In geometric graph theory, a penny graph is a contact graph of unit circles. It is formed from a collection of unit circles that do not cross each other, by creating a vertex for each circle and an edge for every pair of tangent circles. The circles can be represented physically by pennies, arranged without overlapping on a flat surface, with a vertex for each penny and an edge for each two pennies that touch. (en) |
| rdfs:label | Penny graph (en) |
| owl:sameAs | yago-res:Penny graph wikidata:Penny graph dbpedia-fa:Penny graph dbpedia-hu:Penny graph https://global.dbpedia.org/id/2qTp1 |
| prov:wasDerivedFrom | wikipedia-en:Penny_graph?oldid=1117587950&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Sierpinski_Pascal_triangle.svg wiki-commons:Special:FilePath/Penny_graph.jpg wiki-commons:Special:FilePath/Penny_graph_11_nodes.svg wiki-commons:Special:FilePath/Triangle-free_penny_graph.jpg |
| foaf:isPrimaryTopicOf | wikipedia-en:Penny_graph |
| is dbo:wikiPageWikiLink of | dbr:Unit_distance_graph dbr:Contact_graph dbr:Butterfly_graph dbr:Hanoi_graph dbr:Heiko_Harborth dbr:Circle_packing_theorem dbr:Matchstick_graph dbr:Unit_disk_graph |
| is foaf:primaryTopic of | wikipedia-en:Penny_graph |
