Testing outerplanarity of bounded degree graphs

DOI10.1007/s00453-014-9897-1zbMath1319.68162OpenAlexW2178176529MaRDI QIDQ494925

Yuichi Yoshida, Hiro Ito

Publication date: 3 September 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-014-9897-1

zbMATH Keywords

property testingbounded-degree modelouterplanarity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items

Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs, Property testing of planarity in the \textsf{CONGEST} model, Unnamed Item, Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs, Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs, Direct solvers for the biharmonic eigenvalue problems using Legendre polynomials

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Property testing. Current research and surveys
• Every minor-closed property of sparse graphs is testable
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• A linear algorithm for the pos/neg-weighted 1-median problem on a cactus
• A sublinear bipartiteness tester for bounded degree graphs
• Property testing on \(k\)-vertex-connectivity of graphs
• An Efficient Partitioning Oracle for Bounded-Treewidth Graphs
• Property testing and its connection to learning and approximation
• Sublinear Time Algorithms
• Graph minor theory
• The complexity of some edge deletion problems
• A Separator Theorem for Nonplanar Graphs
• Testing the diameter of graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor
• Local Graph Partitions for Approximation and Testing
• Approximating the Minimum Spanning Tree Weight in Sublinear Time
• Probability Inequalities for Sums of Bounded Random Variables
• Property testing in bounded degree graphs