Paper Info
Title
Testing outerplanarity of bounded degree graphs
Abstract
We present an efficient algorithm for testing outerplanarity of graphs in the bounded degree model. In this model, given a graph G with n vertices and degree bound d, we should distinguish with high probability the case that G is outerplanar from the case that modifying at least an ε-fraction of the edge set of G is necessary to make G outerplanar. Our algorithm runs in Õ(1/ε13 d6 + d/ε2) time, which is independent of the size of graphs. This is the first algorithm for a non-trivial minorclosed property whose time complexity is polynomial in 1/ε and d. To achieve the time complexity, we exploit the tree-like structure inherent to an outerplanar graph using the microtree/macrotree decomposition of a tree. As a corollary, we also show an algorithm that tests whether a given graph is a cactus with time complexity Õ(1/ε13 d6 + d/ε2).
Year
DOI
Venue
2010
10.1007/s00453-014-9897-1
Algorithmica
Keywords
Field
DocType
Property testing,Bounded-degree model,Outerplanarity
Discrete mathematics,Combinatorics,Outerplanar graph,Tree-depth,Partial k-tree,Chordal graph,Independent set,Pathwidth,1-planar graph,Metric dimension,Mathematics
Conference
Volume
Issue
ISSN
73
1
0178-4617
ISBN
Citations 
PageRank 
3-642-15368-2
4
0.47
References 
Authors
15
2
Name
Order
Citations
PageRank
Yuichi Yoshida146944.88
Hiro Ito229039.95