Planar graphs: Random walks and bipartiteness testing

DOI10.1002/rsa.20826zbMath1423.05051arXiv1407.2109OpenAlexW2907502211WikidataQ128641250 ScholiaQ128641250MaRDI QIDQ5236926

Morteza Monemizadeh, Christian Sohler, Krzysztof Onak, Artur Czumaj

Publication date: 16 October 2019

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1407.2109

zbMATH Keywords

planar graphsrandomized algorithmsproperty testing

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83)

Related Items (2)

Property testing of planarity in the \textsf{CONGEST} model ⋮ Multiple random walks on graphs: mixing few to cover many

Cites Work

• Unnamed Item
• Property testing. Current research and surveys
• Every minor-closed property of sparse graphs is testable
• Ramanujan graphs
• A sublinear bipartiteness tester for bounded degree graphs
• Testing k-colorability
• Every Property of Hyperfinite Graphs Is Testable
• Property testing and its connection to learning and approximation
• Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
• Testing the diameter of graphs
• Tight Bounds for Testing Bipartiteness in General Graphs
• Approximating the distance to properties in bounded-degree and general sparse graphs
• Testing Forest-Isomorphism in the Adjacency List Model
• Local Graph Partitions for Approximation and Testing
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• Excluded minors, network decomposition, and multicommodity flow
• Property testing in bounded degree graphs

This page was built for publication: Planar graphs: Random walks and bipartiteness testing