{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:27:13Z","timestamp":1750220833658,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":52,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,7,6]],"date-time":"2020-07-06T00:00:00Z","timestamp":1593993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,7,6]]},"DOI":"10.1145\/3350755.3400259","type":"proceedings-article","created":{"date-parts":[[2020,7,9]],"date-time":"2020-07-09T15:56:12Z","timestamp":1594310172000},"page":"269-280","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Parallel Planar Subgraph Isomorphism and Vertex Connectivity"],"prefix":"10.1145","author":[{"given":"Lukas","family":"Gianinazzi","sequence":"first","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Torsten","family":"Hoefler","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,7,9]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Multilayer grid embeddings for vlsi. Algorithmica, 6(1--6):129--151","author":"Aggarwal Alok","year":"1991","unstructured":"Alok Aggarwal , Maria Klawe , and Peter Shor . Multilayer grid embeddings for vlsi. Algorithmica, 6(1--6):129--151 , 1991 . Alok Aggarwal, Maria Klawe, and Peter Shor. Multilayer grid embeddings for vlsi. Algorithmica, 6(1--6):129--151, 1991."},{"issue":"4","key":"e_1_3_2_1_2_1","first-page":"844","volume":"42","author":"Alon Noga","year":"1995","unstructured":"Noga Alon , Raphael Yuster , and Uri Zwick . Color-coding. J. ACM , 42 ( 4 ): 844 -- 856 , 1995 . Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844--856, 1995.","journal-title":"Color-coding. J. ACM"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1021\/ci00010a007"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174650"},{"key":"e_1_3_2_1_5_1","first-page":"224","volume-title":"10th International Symposium on Parameterized and Exact Computation, IPEC 2015","author":"Bannach Max","year":"2015","unstructured":"Max Bannach , Christoph Stockhusen , and Till Tantau . Fast parallel fixed-parameter algorithms via color coding . In 10th International Symposium on Parameterized and Exact Computation, IPEC 2015 , September 16 --18 , 2015 , Patras, Greece, pages 224 -- 235 , 2015. Max Bannach, Christoph Stockhusen, and Till Tantau. Fast parallel fixed-parameter algorithms via color coding. In 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16--18, 2015, Patras, Greece, pages 224--235, 2015."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/227234.227246"},{"key":"e_1_3_2_1_7_1","first-page":"1","volume-title":"14th International Workshop, WG '88, Amsterdam, The Netherlands, June 15--17, 1988","author":"Bodlaender Hans L.","year":"1988","unstructured":"Hans L. Bodlaender . Nc-algorithms for graphs with small treewidth. In Graph-Theoretic Concepts in Computer Science , 14th International Workshop, WG '88, Amsterdam, The Netherlands, June 15--17, 1988 , Proceedings , pages 1 -- 10 , 1988 . Hans L. Bodlaender. Nc-algorithms for graphs with small treewidth. In Graph-Theoretic Concepts in Computer Science, 14th International Workshop, WG '88, Amsterdam, The Netherlands, June 15--17, 1988, Proceedings, pages 1--10, 1988."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167161"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.60"},{"key":"e_1_3_2_1_10_1","first-page":"268","volume-title":"22nd International Colloquium, ICALP95","author":"Hans","year":"1995","unstructured":"Hans L. Bodlaender and Torben Hagerup. Parallel algorithms with optimal speedup for bounded treewidth. In Automata, Languages and Programming , 22nd International Colloquium, ICALP95 , Szeged, Hungary, July 10--14 , 1995 , Proceedings, pages 268 -- 279 , 1995. Hans L. Bodlaender and Torben Hagerup. Parallel algorithms with optimal speedup for bounded treewidth. In Automata, Languages and Programming, 22nd International Colloquium, ICALP95, Szeged, Hungary, July 10--14, 1995, Proceedings, pages 268--279, 1995."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0049"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.41"},{"key":"e_1_3_2_1_13_1","first-page":"275","volume-title":"21st International Workshop, WG '95, Aachen, Germany, June 20--22, 1995","author":"Chen Zhi-Zhong","year":"1995","unstructured":"Zhi-Zhong Chen and Xin He . NC algorithms for partitioning planar graphs into induced forests and approximating np-hard problems. In Graph-Theoretic Concepts in Computer Science , 21st International Workshop, WG '95, Aachen, Germany, June 20--22, 1995 , Proceedings , pages 275 -- 289 , 1995 . Zhi-Zhong Chen and Xin He. NC algorithms for partitioning planar graphs into induced forests and approximating np-hard problems. In Graph-Theoretic Concepts in Computer Science, 21st International Workshop, WG '95, Aachen, Germany, June 20--22, 1995, Proceedings, pages 275--289, 1995."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/237502.237563"},{"key":"e_1_3_2_1_16_1","first-page":"840","volume-title":"Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004","author":"Erik","year":"2004","unstructured":"Erik D. Demaine and Mohammad Taghi Hajiaghayi. Equivalence of local treewidth and linear local treewidth and its algorithmic applications . In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004 , New Orleans, Louisiana, USA, January 11--14 , 2004 , pages 840 -- 849 , 2004. Erik D. Demaine and Mohammad Taghi Hajiaghayi. Equivalence of local treewidth and linear local treewidth and its algorithmic applications. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11--14, 2004, pages 840--849, 2004."},{"key":"e_1_3_2_1_17_1","first-page":"263","volume-title":"27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010","author":"Dorn Frederic","year":"2010","unstructured":"Frederic Dorn . Planar subgraph isomorphism revisited . In 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010 , March 4 --6 , 2010 , Nancy, France, pages 263 -- 274 , 2010. Frederic Dorn. Planar subgraph isomorphism revisited. In 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, March 4--6, 2010, Nancy, France, pages 263--274, 2010."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/313651.313830"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010020"},{"key":"e_1_3_2_1_21_1","first-page":"403","volume-title":"ISAAC 2010, Jeju Island, Korea, December 15--17, 2010, Proceedings, Part I","author":"Eppstein David","year":"2010","unstructured":"David Eppstein , Maarten L\u00f6 ffler, and Darren Strash . Listing all maximal cliques in sparse graphs in near-optimal time. In Algorithms and Computation - 21st International Symposium , ISAAC 2010, Jeju Island, Korea, December 15--17, 2010, Proceedings, Part I , pages 403 -- 414 , 2010 . David Eppstein, Maarten L\u00f6 ffler, and Darren Strash. Listing all maximal cliques in sparse graphs in near-optimal time. In Algorithms and Computation - 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15--17, 2010, Proceedings, Part I, pages 403--414, 2010."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.62"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.92"},{"key":"e_1_3_2_1_24_1","volume-title":"Deterministic graph cuts in subquadratic time: Sparse, balanced, and k-vertex. CoRR, abs\/1910.07950","author":"Gao Yu","year":"2019","unstructured":"Yu Gao , Jason Li , Danupon Nanongkai , Richard Peng , Thatchaphol Saranurak , and Sorrachai Yingchareonthawornchai . Deterministic graph cuts in subquadratic time: Sparse, balanced, and k-vertex. CoRR, abs\/1910.07950 , 2019 . Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai. Deterministic graph cuts in subquadratic time: Sparse, balanced, and k-vertex. CoRR, abs\/1910.07950, 2019."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"e_1_3_2_1_26_1","volume-title":"Computers and Intractability","author":"Garey Michael R.","year":"1990","unstructured":"Michael R. Garey and David S. Johnson . Computers and Intractability ; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. , USA, 1990 . Michael R. Garey and David S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA, 1990."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPPS.1991.153761"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210393"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190030108"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1996.548505"},{"key":"e_1_3_2_1_31_1","first-page":"465","volume-title":"27th Annual Symposium on Foundations of Computer Science","author":"Philip","year":"1986","unstructured":"Philip N. Klein and John H. Reif. An efficient parallel algorithm for planarity . In 27th Annual Symposium on Foundations of Computer Science , Toronto, Canada, 27- -29 October 1986 , pages 465 -- 477 , 1986. Philip N. Klein and John H. Reif. An efficient parallel algorithm for planarity. In 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27--29 October 1986, pages 465--477, 1986."},{"key":"e_1_3_2_1_32_1","first-page":"259","volume-title":"34th Annual Symposium on Foundations of Computer Science","author":"Philip","year":"1993","unstructured":"Philip N. Klein and Sairam Subramanian. A linear-processor polylog-time algorithm for shortest paths in planar graphs . In 34th Annual Symposium on Foundations of Computer Science , Palo Alto, California, USA, 3- -5 November 1993 , pages 259 -- 270 , 1993. Philip N. Klein and Sairam Subramanian. A linear-processor polylog-time algorithm for shortest paths in planar graphs. In 34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3--5 November 1993, pages 259--270, 1993."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/645496.658027"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0002"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"e_1_3_2_1_36_1","volume-title":"Springer Berlin Heidelberg","author":"De Loera Jes\u00fa","year":"2010","unstructured":"Jes\u00fa s A. De Loera , J\u00f6rg Rambau , and Francisco Santos . Triangulations. Springer Berlin Heidelberg , 2010 . Jes\u00fa s A. De Loera, J\u00f6rg Rambau, and Francisco Santos. Triangulations. Springer Berlin Heidelberg, 2010."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755574"},{"key":"e_1_3_2_1_38_1","volume-title":"Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987","author":"Gary","year":"1987","unstructured":"Gary L. Miller and Vijaya Ramachandran. A new graph triconnectivity algorithm and its parallelization . In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987 , New York, New York, USA, pages 335--344 , 1987 . Gary L. Miller and Vijaya Ramachandran. A new graph triconnectivity algorithm and its parallelization. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 335--344, 1987."},{"key":"e_1_3_2_1_39_1","first-page":"478","volume-title":"26th Annual Symposium on Foundations of Computer Science","author":"Gary","year":"1985","unstructured":"Gary L. Miller and John H. Reif. Parallel tree contraction and its application . In 26th Annual Symposium on Foundations of Computer Science , Portland, Oregon, USA, 21- -23 October 1985 , pages 478 -- 489 , 1985. Gary L. Miller and John H. Reif. Parallel tree contraction and its application. In 26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, USA, 21--23 October 1985, pages 478--489, 1985."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.298.5594.824"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00183-1"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316394"},{"key":"e_1_3_2_1_43_1","volume-title":"Computing and testing small vertex connectivity in near-linear time and queries. CoRR, abs\/1905.05329","author":"Nanongkai Danupon","year":"2019","unstructured":"Danupon Nanongkai , Thatchaphol Saranurak , and Sorrachai Yingchareonthawornchai . Computing and testing small vertex connectivity in near-linear time and queries. CoRR, abs\/1905.05329 , 2019 . Danupon Nanongkai, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai. Computing and testing small vertex connectivity in near-linear time and queries. CoRR, abs\/1905.05329, 2019."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/157485.164556","volume-title":"Proceedings of the 30th Design Automation Conference","author":"Ohlrich Miles","year":"1993","unstructured":"Miles Ohlrich , Carl Ebeling , Eka Ginting , and Lisa Sather . Subgemini : Identifying subcircuits using a fast subgraph isomorphism algorithm . In Proceedings of the 30th Design Automation Conference . Dallas, Texas, USA, June 14--18 , 1993 , pages 31 -- 37 , 1993. Miles Ohlrich, Carl Ebeling, Eka Ginting, and Lisa Sather. Subgemini: Identifying subcircuits using a fast subgraph isomorphism algorithm. In Proceedings of the 30th Design Automation Conference. Dallas, Texas, USA, June 14--18, 1993, pages 31--37, 1993."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90023-1"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth436"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/562546"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2009.5206863"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214061"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_3_2_1_52_1","volume-title":"Introduction to Graph Theory. Longman","author":"Wilson R.J.","year":"1996","unstructured":"R.J. Wilson . Introduction to Graph Theory. Longman , 1996 . R.J. Wilson. Introduction to Graph Theory. Longman, 1996."}],"event":{"name":"SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"],"location":"Virtual Event USA","acronym":"SPAA '20"},"container-title":["Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3350755.3400259","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3350755.3400259","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:13:35Z","timestamp":1750202015000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3350755.3400259"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,6]]},"references-count":52,"alternative-id":["10.1145\/3350755.3400259","10.1145\/3350755"],"URL":"https:\/\/doi.org\/10.1145\/3350755.3400259","relation":{},"subject":[],"published":{"date-parts":[[2020,7,6]]},"assertion":[{"value":"2020-07-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}