About: Penny graph

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Penny graph Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : dbpedia.org:8891 associated with source document(s)
QRcode icon

http://dbpedia.org:8891/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FPenny_graph

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.

Attributes	Values
rdfs:label	Penny graph (en)
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)
foaf:depiction
dcterms:subject	Circle packing Geometric graphs Planar graphs
Wikipage page ID	53242630 (xsd:integer)
Wikipage revision ID	1117587950 (xsd:integer)
Link from a Wikipage to another Wikipage	Degeneracy (graph theory) Circle packing Geometric graphs Paul Erdős Penny Unit circle Unit distance graph Delaunay triangulation Planar graphs Maximum disjoint set Geometric graph theory Nearest neighbor graph Graph coloring NP-hard Contact graph Convex hull Closest pair of points problem Tangent circles Tree (graph theory) Triangle-free graph Triangular tiling Floor function Four-color theorem Four color theorem Grötzsch's theorem Intersection graph Baker's technique Squaregraph Planar graph Polynomial-time approximation scheme Circle packing theorem Connected component (graph theory) Matchstick graph Unit disk graph Kissing number problem Maximum independent set Square grid
sameAs	Penny graph Penny graph Penny graph Penny graph Penny graph
dbp:wikiPageUsesTemplate	dbt:Math dbt:Mvar dbt:R dbt:Reflist dbt:Sfnp dbt:Short_description dbt:Unsolved
thumbnail	wiki-commons:Special:FilePath/Penny_graph.jpg?width=300
has 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)
prov:wasDerivedFrom	wikipedia-en:Penny_graph?oldid=1117587950&ns=0
page length (characters) of wiki page	17953 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:Penny_graph
is Link from a Wikipage to another Wikipage of	Unit distance graph Contact graph Butterfly graph Hanoi graph Heiko Harborth Circle packing theorem Matchstick graph Unit disk graph
is foaf:primaryTopic of	wikipedia-en:Penny_graph

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3331 as of Sep 2 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (62 GB total memory, 37 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software