Autor(en): | Sohler, Christian |
Titel: | What does the local structure of a planar graph tell us about its global structure? |
Sprache (ISO): | en |
Zusammenfassung: | 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 |
Erscheinungsdatum: | 2014 |
Enthalten in den Sammlungen: | Sublinear Algorithms for the Analysis of Very Large Graphs |
Dateien zu dieser Ressource:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
mfcs.pdf | 100.85 kB | Adobe PDF | Öffnen/Anzeigen |
Diese Ressource ist urheberrechtlich geschützt. |
Diese Ressource ist urheberrechtlich geschützt. rightsstatements.org