What does the local structure of a planar graph tell us about its global structure?
| dc.contributor.author | Sohler, Christian | |
| dc.date.accessioned | 2015-07-22T07:34:25Z | |
| dc.date.available | 2015-07-22T07:34:25Z | |
| dc.date.issued | 2014 | |
| dc.description.abstract | The local k-neighborhood of a vertex v in an unweighted graph G = (V,E) with vertex set V and edge set E is the subgraph induced by all vertices of distance at most k from v. The rooted k-neighborhood of v is also called a k-disk around vertex v. If a graph has maximum degree bounded by a constant d, and k is also constant, the number of isomorphism classes of k-disks is constant as well. We can describe the local structure of a bounded-degree graph G by counting the number of isomorphic copies in G of each possible k-disk. We can summarize this information in form of a vector that has an entry for each isomorphism class of k-disks. The value of the entry is the number of isomorphic copies of the corresponding k-disk in G. We call this vector frequency vector of k-disks. If we only know this vector, what does it tell us about the structure of G? In this paper we will survey a series of papers in the area of Property Testing that leads to the following result (stated informally): There is a k = k(ε,d) such that for any planar graph G its local structure (described by the frequency vector of k-disks) determines G up to insertion and deletion of at most εd n edges (and relabelling of vertices). | en |
| dc.description.sponsorship | This project has received funding from the European Union’s Seventh Framework Programme for research, technological development and demonstration under grant agreement no. 307696. | en |
| dc.identifier.uri | http://hdl.handle.net/2003/34159 | |
| dc.identifier.uri | http://dx.doi.org/10.17877/DE290R-7623 | |
| dc.language.iso | en | de |
| dc.subject.ddc | 004 | |
| dc.title | What does the local structure of a planar graph tell us about its global structure? | en |
| dc.type | Text | de |
| dc.type.publicationtype | article | de |
| dcterms.accessRights | open access |