License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.21
URN: urn:nbn:de:0030-drops-66448
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6644/
Go to the corresponding LIPIcs Volume Portal

Babu, Jasine ; Khoury, Areej ; Newman, Ilan

Every Property of Outerplanar Graphs is Testable

pdf-format:
LIPIcs-APPROX-RANDOM-2016-21.pdf (0.6 MB)

Abstract

A D-disc around a vertex v of a graph G=(V,E) is the subgraph induced by all vertices of distance at most D from v. We show that the structure of an outerplanar graph on n vertices is determined, up to modification (insertion or deletion) of at most epsilon n edges, by a set of D-discs around the vertices, for D=D(epsilon) that is independent of the size of the graph. Such a result was already known for planar graphs (and any hyperfinite graph class), in the limited case of bounded degree graphs (that is, their maximum degree is bounded by some fixed constant, independent of |V|). We prove this result with no assumption on the degree of the graph.

A pure combinatorial consequence of this result is that two outerplanar graphs that share the same local views are close to be isomorphic.

We also obtain the following property testing results in the sparse graph model:

* graph isomorphism is testable for outerplanar graphs by poly(log n) queries.

* every graph property is testable for outerplanar graphs by poly(log n) queries.

We note that we can replace outerplanar graphs by a slightly more general family of k-edge-outerplanar graphs. The only previous general testing results, as above, where known for forests (Kusumoto and Yoshida), and for some power-law graphs that are extremely close to be bounded degree hyperfinite (by Ito).

BibTeX - Entry

@InProceedings{babu_et_al:LIPIcs:2016:6644,
  author =	{Jasine Babu and Areej Khoury and Ilan Newman},
  title =	{{Every Property of Outerplanar Graphs is Testable}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{21:1--21:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6644},
  URN =		{urn:nbn:de:0030-drops-66448},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.21},
  annote =	{Keywords: Property testing, Isomorphism, Outerplanar graphs}
}

Keywords: Property testing, Isomorphism, Outerplanar graphs
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Issue Date: 2016
Date of publication: 06.09.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI