{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T01:17:34Z","timestamp":1747444654461},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,10,21]],"date-time":"2014-10-21T00:00:00Z","timestamp":1413849600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,9]]},"DOI":"10.1007\/s00453-014-9897-1","type":"journal-article","created":{"date-parts":[[2014,10,22]],"date-time":"2014-10-22T04:37:36Z","timestamp":1413952656000},"page":"1-20","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Testing Outerplanarity of Bounded Degree Graphs"],"prefix":"10.1007","volume":"73","author":[{"given":"Yuichi","family":"Yoshida","sequence":"first","affiliation":[]},{"given":"Hiro","family":"Ito","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,10,21]]},"reference":[{"issue":"2","key":"9897_CR1","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R Rubinfeld","year":"1996","unstructured":"Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM J. Comput. 25(2), 252\u2013271 (1996)","journal-title":"SIAM J. Comput."},{"key":"9897_CR2","doi-asserted-by":"crossref","unstructured":"Goldreich, O. (ed.): Property Testing: Current Research and Surveys. Volume 6390 of LNCS. Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-16367-8"},{"issue":"4","key":"9897_CR3","doi-asserted-by":"crossref","first-page":"1562","DOI":"10.1137\/100791075","volume":"25","author":"R Rubinfeld","year":"2012","unstructured":"Rubinfeld, R., Shapira, A.: SIAM J. Discrete Math. 25(4), 1562\u20131588 (2012)","journal-title":"SIAM J. Discrete Math."},{"key":"9897_CR4","first-page":"97","volume":"75","author":"E Fischer","year":"2001","unstructured":"Fischer, E.: The art of uninformed decisions: a primer to property testing. Bull. Eur. Assoc. Theor. Comput. Sci. 75, 97\u2013126 (2001)","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"issue":"2","key":"9897_CR5","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1007\/s00453-001-0078-7","volume":"32","author":"O Goldreich","year":"2008","unstructured":"Goldreich, O., Ron, D.: Property testing in bounded degree graphs. Algorithmica 32(2), 302\u2013343 (2008)","journal-title":"Algorithmica"},{"issue":"6","key":"9897_CR6","doi-asserted-by":"crossref","first-page":"2200","DOI":"10.1016\/j.aim.2009.10.018","volume":"223","author":"I Benjamini","year":"2010","unstructured":"Benjamini, I., Schramm, O., Shapira, A.: Every minor-closed property of sparse graphs is testable. Adv. Math. 223(6), 2200\u20132218 (2010)","journal-title":"Adv. Math."},{"key":"9897_CR7","doi-asserted-by":"crossref","unstructured":"Hassidim, A., Kelner, J.A., Nguyen, H.N., Onak, K.: Local graph partitions for approximation and testing. In: Proceedings of 50th Annual IEEE Symposium on Foundations of Computer, Science (FOCS) (2009) 22\u201331","DOI":"10.1109\/FOCS.2009.77"},{"key":"9897_CR8","doi-asserted-by":"crossref","unstructured":"Levi, R., Ron, D.: A quasi-polynomial time partition oracle for graphs with an excluded minor. In: Proceedings of 40th International Colloquium Conference on Automata, Languages, and Programming (ICALP) (2013) 709\u2013720","DOI":"10.1007\/978-3-642-39206-1_60"},{"key":"9897_CR9","doi-asserted-by":"crossref","unstructured":"Edelman, A., Hassidim, A., Nguyen, H., Onak, K.: An efficient partitioning oracle for bounded-treewidth graphs. In: Proceedings of 15th International Workshop on Randomization and Computation (RANDOM) (2011) 530\u2013541","DOI":"10.1007\/978-3-642-22935-0_45"},{"issue":"3","key":"9897_CR10","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1007\/s00453-010-9477-y","volume":"62","author":"Y Yoshida","year":"2012","unstructured":"Yoshida, Y., Ito, H.: Property testing on $$k$$ k -vertex connectivity of graphs. Algorithmica 62(3), 701\u2013712 (2012)","journal-title":"Algorithmica"},{"issue":"3","key":"9897_CR11","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/s004930050060","volume":"19","author":"O Goldreich","year":"1999","unstructured":"Goldreich, O., Ron, D.: A sublinear bipartiteness tester for bounded degree graphs. Combinatorica 19(3), 335\u2013373 (1999)","journal-title":"Combinatorica"},{"key":"9897_CR12","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Sohler, C.: Testing expansion in bounded-degree graphs. In: Proceedings of 48th Annual IEEE Symposium on Foundations of Computer, Science (FOCS) (2007) 570\u2013578","DOI":"10.1109\/FOCS.2007.33"},{"issue":"5","key":"9897_CR13","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0020-0190(79)90075-9","volume":"9","author":"SL Mitchell","year":"1979","unstructured":"Mitchell, S.L.: Linear algorithms to recognize outerplanar and maximal outerplanar graphs. Inf. Process. Lett. 9(5), 229\u2013232 (1979)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"9897_CR14","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. J. ACM 45(4), 653\u2013750 (1998)","journal-title":"J. ACM"},{"issue":"2","key":"9897_CR15","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1002\/rsa.10013","volume":"20","author":"M Parnas","year":"2002","unstructured":"Parnas, M., Ron, D.: Testing the diameter of graphs. Random Struct. Algorithms 20(2), 165\u2013183 (2002)","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"9897_CR16","doi-asserted-by":"crossref","first-page":"801","DOI":"10.1090\/S0894-0347-1990-1065053-0","volume":"3","author":"N Alon","year":"1990","unstructured":"Alon, N., Seymour, P., Thomas, R.: A separator theorem for nonplanar graphs. J. Am. Math. Soc. 3(4), 801\u2013808 (1990)","journal-title":"J. Am. Math. Soc."},{"key":"9897_CR17","doi-asserted-by":"crossref","unstructured":"Kleinberg, J., Rubinfeld, R.: Short paths in expander graphs. In: Proceedings of 37th Annual IEEE Symposium on Foundations of Computer, Science (FOCS) (1996) 86\u201395","DOI":"10.1109\/SFCS.1996.548467"},{"key":"9897_CR18","unstructured":"Plotkin, S., Rao, S., Smith, W.D.: Shallow excluded minors and improved graph decompositions. In: Proceedings of 5th Annual ACM-SIAM symposium on Discrete algorithms (SODA) (1994) 462\u2013470"},{"key":"9897_CR19","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Husfeldt, T., Rauhe, T.: Marked ancestor problems. In: Proceedings of 39th Annual IEEE Symposium on Foundations of Computer, Science (FOCS) (1998) 534\u2013543","DOI":"10.1109\/SFCS.1998.743504"},{"key":"9897_CR20","volume-title":"Graph Theory. Graduate Texts in Mathematics","author":"R Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 3rd edn. Springer, Berlin (2005)","edition":"3"},{"issue":"1","key":"9897_CR21","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1090\/S0273-0979-05-01088-8","volume":"43","author":"L Lov\u00e1sz","year":"2006","unstructured":"Lov\u00e1sz, L.: Graph minor theory. Bull. Am. Math. Soc. 43(1), 75\u201386 (2006)","journal-title":"Bull. Am. Math. Soc."},{"issue":"6","key":"9897_CR22","doi-asserted-by":"crossref","first-page":"1370","DOI":"10.1137\/S0097539702403244","volume":"34","author":"B Chazelle","year":"2005","unstructured":"Chazelle, B., Rubinfeld, R., Trevisan, L.: Approximating the minimum spanning tree weight in sublinear time. SIAM J. Comput. 34(6), 1370\u20131379 (2005)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9897_CR23","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/BF02684332","volume":"60","author":"RE Burkard","year":"1998","unstructured":"Burkard, R.E., Krarup, J.: A linear algorithm for the pos\/neg-weighted 1-median problem on a cactus. Computing 60(3), 193\u2013215 (1998)","journal-title":"Computing"},{"issue":"301","key":"9897_CR24","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13\u201330 (1963)","journal-title":"J. Am. Stat. Assoc."},{"issue":"3","key":"9897_CR25","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1109\/31.1748","volume":"35","author":"E El-Mallah","year":"1988","unstructured":"El-Mallah, E., Colbourn, C.J.: The complexity of some edge deletion problems. IEEE Trans. Circuits Syst. 35(3), 354\u2013362 (1988)","journal-title":"IEEE Trans. Circuits Syst."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9897-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9897-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9897-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,16]],"date-time":"2019-08-16T13:07:16Z","timestamp":1565960836000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9897-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,21]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,9]]}},"alternative-id":["9897"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9897-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,21]]}}}