Authors: | Sohler, Christian |
Title: | What does the local structure of a planar graph tell us about its global structure? |
Language (ISO): | en |
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). |
URI: | http://hdl.handle.net/2003/34159 http://dx.doi.org/10.17877/DE290R-7623 |
Issue Date: | 2014 |
Appears in Collections: | Sublinear Algorithms for the Analysis of Very Large Graphs |
This item is protected by original copyright |
All resources in the repository are protected by copyright.