{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T04:49:25Z","timestamp":1725511765393},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540709176"},{"type":"electronic","value":"9783540709183"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70918-3_58","type":"book-chapter","created":{"date-parts":[[2007,5,23]],"date-time":"2007-05-23T19:41:23Z","timestamp":1179949283000},"page":"682-693","source":"Crossref","is-referenced-by-count":10,"title":["Planar Graphs: Logical Complexity and Parallel Isomorphism Tests"],"prefix":"10.1007","author":[{"given":"Oleg","family":"Verbitsky","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"58_CR1","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/BF01305232","volume":"12","author":"J.-Y. Cai","year":"1992","unstructured":"Cai, J.-Y., F\u00fcrer, M., Immerman, N.: An optimal lower bound on the number of variables for graph identification. Combinatorica\u00a012, 389\u2013410 (1992)","journal-title":"Combinatorica"},{"key":"58_CR2","volume-title":"Graph theory","author":"R. Diestel","year":"2006","unstructured":"Diestel, R.: Graph theory. Springer, Heidelberg (2006)"},{"key":"58_CR3","doi-asserted-by":"crossref","unstructured":"Grohe, M.: Fixed-point logics on planar graphs. In: Proc. of the Ann. Conf. on Logic in Computer Science, pp. 6\u201315 (1998)","DOI":"10.1109\/LICS.1998.705639"},{"key":"58_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/3-540-49257-7_6","volume-title":"Database Theory - ICDT\u201999","author":"M. Grohe","year":"1998","unstructured":"Grohe, M., Marino, J.: Definability and descriptive complexity on databases of bounded tree-width. In: Beeri, C., Bruneman, P. (eds.) ICDT 1999. LNCS, vol.\u00a01540, pp. 70\u201382. Springer, Heidelberg (1998)"},{"key":"58_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/11786986_2","volume-title":"Automata, Languages and Programming","author":"M. Grohe","year":"2006","unstructured":"Grohe, M., Verbitsky, O.: Testing graph isomorphism in parallel by playing a game. In: Bugliesi, M., et al. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 3\u201314. Springer, Heidelberg (2006)"},{"key":"58_CR6","unstructured":"Hopcroft, J.E.: An n logn algorithm for isomorphism of planar triply connected graphs. Technical Report CS-192. Stanford University (1971)"},{"key":"58_CR7","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/978-1-4684-2001-2_13","volume-title":"Complexity of computer computations","author":"J.E. Hopcroft","year":"1972","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Isomorphism of planar graphs (working paper). In: Complexity of computer computations, pp. 131\u2013152. Plenum Press, New York (1972)"},{"key":"58_CR8","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/0202012","volume":"2","author":"J.E. Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Deviding a graph into triconnected components. SIAM Journal on Computing\u00a02, 135\u2013158 (1973)","journal-title":"SIAM Journal on Computing"},{"key":"58_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive complexity","author":"N. Immerman","year":"1999","unstructured":"Immerman, N.: Descriptive complexity. Springer, Heidelberg (1999)"},{"key":"58_CR10","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1002\/rsa.20049","volume":"26","author":"J.-H. Kim","year":"2005","unstructured":"Kim, J.-H., et al.: How complex are random graphs in first order logic? Random Structures and Algorithms\u00a026, 119\u2013145 (2005)","journal-title":"Random Structures and Algorithms"},{"key":"58_CR11","doi-asserted-by":"publisher","first-page":"1128","DOI":"10.1137\/0220070","volume":"20","author":"G.L. Miller","year":"1991","unstructured":"Miller, G.L., Reif, J.H.: Parallel tree contraction. Part 2: further applications. SIAM J. Comput.\u00a020, 1128\u20131147 (1991)","journal-title":"SIAM J. Comput."},{"key":"58_CR12","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.apal.2005.04.003","volume":"139","author":"O. Pikhurko","year":"2006","unstructured":"Pikhurko, O., Spencer, J., Verbitsky, O.: Succinct definitions in first order graph theory. Annals of Pure and Applied Logic\u00a0139, 74\u2013109 (2006)","journal-title":"Annals of Pure and Applied Logic"},{"key":"58_CR13","doi-asserted-by":"publisher","first-page":"2511","DOI":"10.1016\/j.dam.2006.03.002","volume":"154","author":"O. Pikhurko","year":"2006","unstructured":"Pikhurko, O., Veith, H., Verbitsky, O.: First order definability of graphs: tight bounds on quantifier rank. Discrete Applied Mathematics\u00a0154, 2511\u20132529 (2006)","journal-title":"Discrete Applied Mathematics"},{"key":"58_CR14","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1016\/S0022-0000(05)80070-4","volume":"49","author":"V. Ramachandran","year":"1994","unstructured":"Ramachandran, V., Reif, J.: Planarity testing in parallel. J. Comput. Syst. Sci.\u00a049, 517\u2013561 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"58_CR15","unstructured":"Weisfeiler, B., Yu., L.A.A.: A reduction of a graph to a canonical form and an algebra arising during this reduction (in Russian). Nauchno-Technicheskaya Informatsia, Seriya 2. 9, 12\u201316 (1968)"},{"key":"58_CR16","unstructured":"Verbitsky, O.: Planar graphs: Logical complexity and parallel isomorphism tests. E-print (2006), \n                    \n                      http:\/\/arxiv.org\/abs\/cs.CC\/0607033"}],"container-title":["Lecture Notes in Computer Science","STACS 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70918-3_58.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T00:12:01Z","timestamp":1605744721000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70918-3_58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540709176","9783540709183"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70918-3_58","relation":{},"subject":[]}}