{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:04:10Z","timestamp":1725563050803},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642153686"},{"type":"electronic","value":"9783642153693"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15369-3_48","type":"book-chapter","created":{"date-parts":[[2010,8,27]],"date-time":"2010-08-27T04:01:36Z","timestamp":1282881696000},"page":"642-655","source":"Crossref","is-referenced-by-count":2,"title":["Testing Outerplanarity of Bounded Degree Graphs"],"prefix":"10.1007","author":[{"given":"Yuichi","family":"Yoshida","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiro","family":"Ito","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"48_CR1","doi-asserted-by":"publisher","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.\u00a025(2), 252\u2013271 (1996)","journal-title":"SIAM J. Comput."},{"key":"48_CR2","unstructured":"Fischer, E.: The art of uninformed decisions: A primer to property testing. Bulletin of the European Association for Theoretical Computer Science\u00a075 (2001)"},{"key":"48_CR3","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1090\/dimacs\/043\/04","volume":"43","author":"O. Goldreich","year":"1999","unstructured":"Goldreich, O.: Combinatorial property testing (a survey). DIMACS Series in Discrete Mathematics and Theoretical Computer Science\u00a043, 45\u201359 (1999)","journal-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science"},{"issue":"2","key":"48_CR4","doi-asserted-by":"publisher","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\u00a032(2), 302\u2013343 (2008)","journal-title":"Algorithmica"},{"key":"48_CR5","doi-asserted-by":"crossref","unstructured":"Benjamini, I., Schramm, O., Shapira, A.: Every minor-closed property of sparse graphs is testable. In: Proc.\u00a0of STOC 2008, pp. 393\u2013402 (2008)","DOI":"10.1145\/1374376.1374433"},{"key":"48_CR6","doi-asserted-by":"crossref","unstructured":"Hassidim, A., Kelner, J.A., Nguyen, H.N., Onak, K.: Local graph partitions for approximation and testing. In: Proc. of FOCS 2009 (2009) (to appear)","DOI":"10.1109\/FOCS.2009.77"},{"key":"48_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/978-3-540-70575-8_44","volume-title":"Automata, Languages and Programming","author":"Y. Yoshida","year":"2008","unstructured":"Yoshida, Y., Ito, H.: Property testing on k-vertex-connectivity of graphs. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 539\u2013550. Springer, Heidelberg (2008)"},{"key":"48_CR8","first-page":"289","volume-title":"Proc.\u00a0of STOC 1998","author":"O. Goldreich","year":"1998","unstructured":"Goldreich, O., Ron, D.: A sublinear bipartiteness tester for bounded degree graphs. In: Proc.\u00a0of STOC 1998, pp. 289\u2013298. ACM, New York (1998)"},{"key":"48_CR9","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Sohler, C.: Testing expansion in bounded-degree graphs. In: Proc.\u00a0of FOCS 2007, pp. 570\u2013578 (2007)","DOI":"10.1109\/FOCS.2007.33"},{"issue":"4","key":"48_CR10","doi-asserted-by":"publisher","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\u00a045(4), 653\u2013750 (1998)","journal-title":"J. ACM"},{"issue":"5","key":"48_CR11","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0020-0190(79)90075-9","volume":"9","author":"S.L. Mitchell","year":"1979","unstructured":"Mitchell, S.L.: Linear algorithms to recognize outerplanar and maximal outerplanar graphs. Information Processing Letters\u00a09(5), 229\u2013232 (1979)","journal-title":"Information Processing Letters"},{"key":"48_CR12","doi-asserted-by":"crossref","unstructured":"Alon, N., Seymour, P., Thomas, R.: A separator theorem for graphs with an excluded minor and its applications. In: Proc.\u00a0of STOC 1990, pp. 293\u2013299 (1990)","DOI":"10.1145\/100216.100254"},{"key":"48_CR13","doi-asserted-by":"crossref","unstructured":"Kleinberg, J., Rubinfeld, R.: Short paths in expander graphs. In: Proc.\u00a0of FOCS 1996, p. 86 (1996)","DOI":"10.1109\/SFCS.1996.548467"},{"key":"48_CR14","unstructured":"Plotkin, S., Rao, S., Smith, W.D.: Shallow excluded minors and improved graph decompositions. In: Proc. of SODA 1994, pp. 462\u2013470 (1994)"},{"key":"48_CR15","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Husfeldt, T., Rauhe, T.: Marked ancestor problems. In: Proc. of FOCS 1998, pp. 534\u2013543 (1998)","DOI":"10.1109\/SFCS.1998.743504"},{"key":"48_CR16","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, 3rd edn. Graduate Texts in Mathematics, vol.\u00a0173. Springer, Heidelberg (2005)","edition":"3"},{"issue":"1","key":"48_CR17","doi-asserted-by":"publisher","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. Amer. Math. Soc.\u00a043(1), 75\u201386 (2006)","journal-title":"Bull. Amer. Math. Soc."},{"key":"48_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/3-540-48224-5_16","volume-title":"Automata, Languages and Programming","author":"B. Chazelle","year":"2001","unstructured":"Chazelle, B., Rubinfeld, R., Trevisan, L.: Approximating the minimum spanning tree weight in sublinear time. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 190\u2013200. Springer, Heidelberg (2001)"},{"issue":"301","key":"48_CR19","doi-asserted-by":"publisher","first-page":"13","DOI":"10.2307\/2282952","volume":"58","author":"W. Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. Amer. Statistical Assoc. J.\u00a058(301), 13\u201330 (1963)","journal-title":"Amer. Statistical Assoc. J."},{"issue":"3","key":"48_CR20","doi-asserted-by":"publisher","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 Transactions on Circuits and Systems\u00a035(3), 354\u2013362 (1988)","journal-title":"IEEE Transactions on Circuits and Systems"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15369-3_48.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T12:51:26Z","timestamp":1619787086000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15369-3_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642153686","9783642153693"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15369-3_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}