{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T19:51:01Z","timestamp":1770321061426,"version":"3.49.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2008,1,15]],"date-time":"2008-01-15T00:00:00Z","timestamp":1200355200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2009,12]]},"DOI":"10.1007\/s00453-007-9162-y","type":"journal-article","created":{"date-parts":[[2008,1,14]],"date-time":"2008-01-14T17:56:27Z","timestamp":1200333387000},"page":"703-728","source":"Crossref","is-referenced-by-count":5,"title":["Structure and Recognition of Graphs with No 6-wheel Subdivision"],"prefix":"10.1007","volume":"55","author":[{"given":"Rebecca","family":"Robinson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Graham","family":"Farr","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,1,15]]},"reference":[{"key":"9162_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0012-365X(90)90292-P","volume":"80","author":"S. Arnborg","year":"1990","unstructured":"Arnborg, S., Proskurowski, A., Corneilz, D.G.: Forbidden minors characterization of partial 3-trees. Discrete Math. 80, 1\u20139 (1990)","journal-title":"Discrete Math."},{"key":"9162_CR2","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0304-3975(85)90222-1","volume":"38","author":"T. Asano","year":"1985","unstructured":"Asano, T.: An approach to the subgraph homeomorphism problem. Theor. Comput. Sci. 38, 249\u2013267 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"9162_CR3","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1006\/jagm.1998.0991","volume":"30","author":"H.D. Booth","year":"1999","unstructured":"Booth, H.D., Govindan, R., Langston, M.A., Ramachandramurthi, S.: Fast algorithms for K 4 immersion testing. J. Algorithms 30, 344\u2013378 (1999)","journal-title":"J. Algorithms"},{"key":"9162_CR4","first-page":"433","volume":"3","author":"G. Chartrand","year":"1967","unstructured":"Chartrand, G., Harary, F.: Planar permutation graphs. Ann. Inst. Henri Poincar\u00e9 Sec. B. 3, 433\u2013438 (1967)","journal-title":"Ann. Inst. Henri Poincar\u00e9 Sec. B"},{"key":"9162_CR5","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/0196-6774(87)90030-7","volume":"8","author":"M.J. Chung","year":"1987","unstructured":"Chung, M.J.: O(n 2.5) time algorithms for the subgraph homeomorphism problem on trees. J. Algorithms 8, 106\u2013112 (1987)","journal-title":"J. Algorithms"},{"key":"9162_CR6","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1145\/800141.804668","volume-title":"STOC \u201980: Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing","author":"A. Cypher","year":"1980","unstructured":"Cypher, A.: An approach to the k paths problem. In: STOC \u201980: Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, pp. 211\u2013217. ACM Press, New York (1980)"},{"key":"9162_CR7","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1112\/plms\/s3-2.1.69","volume":"27","author":"G.A. Dirac","year":"1952","unstructured":"Dirac, G.A.: A property of 4-chromatic graphs and remarks on critical graphs. J. Lond. Math. Soc. 27, 69\u201381 (1952)","journal-title":"J. Lond. Math. Soc."},{"key":"9162_CR8","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0022-247X(65)90125-3","volume":"10","author":"R.J. Duffin","year":"1965","unstructured":"Duffin, R.J.: Topology of series-parallel networks. J. Math. Anal. Appl. 10, 303\u2013318 (1965)","journal-title":"J. Math. Anal. Appl."},{"key":"9162_CR9","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0012-365X(88)90066-0","volume":"71","author":"G. Farr","year":"1988","unstructured":"Farr, G.: The subgraph homeomorphism problem for small wheels. Discrete Math. 71, 129\u2013142 (1988)","journal-title":"Discrete Math."},{"key":"9162_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/conm\/089\/1006472","volume":"89","author":"M.R. Fellows","year":"1989","unstructured":"Fellows, M.R.: The Robertson-Seymour theorems: a survey of applications. Contemp. Math. 89, 1\u201318 (1989)","journal-title":"Contemp. Math."},{"key":"9162_CR11","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1080\/03081089108818077","volume":"29","author":"M. Fellows","year":"1991","unstructured":"Fellows, M., Kaschube, P.: Searching for K 3,3 in linear time. Linear Multilinear Algebra 29, 279\u2013290 (1991)","journal-title":"Linear Multilinear Algebra"},{"key":"9162_CR12","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S. Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraph homeomorphism problem. Theor. Comput. Sci. 10, 111\u2013121 (1980)","journal-title":"Theor. Comput. Sci."},{"key":"9162_CR13","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0012-365X(93)90565-B","volume":"120","author":"B.S. Gubser","year":"1993","unstructured":"Gubser, B.S.: Planar graphs with no 6-wheel minor. Discrete Math. 120, 59\u201373 (1993)","journal-title":"Discrete Math."},{"key":"9162_CR14","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1090\/S0002-9904-1943-08065-2","volume":"49","author":"D.W. Hall","year":"1943","unstructured":"Hall, D.W.: A note on primitive skew curves. Bull. Am. Math. Soc. 49, 935\u2013937 (1943)","journal-title":"Bull. Am. Math. Soc."},{"key":"9162_CR15","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J.E. Hopcroft","year":"1974","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Efficient planarity testing. J. Assoc. Comput. Mach. 21, 549\u2013568 (1974)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9162_CR16","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0196-6774(87)90043-5","volume":"8","author":"D.S. Johnson","year":"1987","unstructured":"Johnson, D.S.: The NP-completeness column: an ongoing guide. J. Algorithms 8, 285\u2013303 (1987)","journal-title":"J. Algorithms"},{"key":"9162_CR17","unstructured":"Kaschube, P.A.: Finding a subgraph homomorphic to K 3,3 in polynomial time. PhD thesis, University of California, San Diego (1984)"},{"key":"9162_CR18","first-page":"345","volume-title":"SODA \u201992: Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms","author":"A. K\u00e9zdy","year":"1992","unstructured":"K\u00e9zdy, A., McGuinness, P.: Sequential and parallel algorithms to find a K 5 minor. In: SODA \u201992: Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 345\u2013356. Society for Industrial and Applied Mathematics, Philadelphia (1992)"},{"key":"9162_CR19","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1137\/0221032","volume":"21","author":"S. Khuller","year":"1992","unstructured":"Khuller, S., Mitchell, S.G., Vazirani, V.V.: Processor efficient parallel algorithms for the two disjoint paths problem and for finding a Kuratowski homeomorph. SIAM J. Comput. 21, 486\u2013506 (1992)","journal-title":"SIAM J. Comput."},{"key":"9162_CR20","doi-asserted-by":"crossref","first-page":"271","DOI":"10.4064\/fm-15-1-271-283","volume":"15","author":"C. Kuratowski","year":"1930","unstructured":"Kuratowski, C.: Sur le probl\u00e8me des courbes gauches en topologie. Fund. Math. 15, 271\u2013283 (1930)","journal-title":"Fund. Math."},{"key":"9162_CR21","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0022-0000(80)90057-4","volume":"20","author":"A.S. LaPaugh","year":"1980","unstructured":"LaPaugh, A.S., Rivest, R.L.: The subgraph homeomorphism problem. J. Comput. Syst. Sci. 20, 133\u2013149 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"9162_CR22","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0304-3975(89)90127-8","volume":"68","author":"A. Lingas","year":"1989","unstructured":"Lingas, A., Proskurowski, A.: On parallel complexity of the subgraph homeomorphism and the subgraph isomorphism problem for classes of planar graphs. Theor. Comput. Sci. 68, 155\u2013173 (1989)","journal-title":"Theor. Comput. Sci."},{"key":"9162_CR23","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1006\/jctb.1993.1019","volume":"57","author":"B. Oporowski","year":"1993","unstructured":"Oporowski, B., Oxley, J., Thomas, R.: Typical subgraphs of 3- and 4-connected graphs. J. Comb. Theory Ser. B 57, 239\u2013257 (1993)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9162_CR24","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1090\/S0002-9947-1987-0879563-6","volume":"301","author":"J.G. Oxley","year":"1987","unstructured":"Oxley, J.G.: The binary matroids with no 4-wheel minor. Trans. Am. Math. Soc. 301, 63\u201375 (1987)","journal-title":"Trans. Am. Math. Soc."},{"key":"9162_CR25","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1016\/0095-8956(89)90051-8","volume":"46","author":"J. Oxley","year":"1989","unstructured":"Oxley, J.: The regular matroids with no 5-wheel minor. J. Comb. Theory Ser. B 46, 292\u2013305 (1989)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9162_CR26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/322047.322048","volume":"25","author":"Y. Perl","year":"1978","unstructured":"Perl, Y., Shiloach, Y.: Finding two disjoint paths between two pairs of vertices in a graph. J. Assoc. Comput. Mach. 25, 1\u20139 (1978)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9162_CR27","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1137\/0606030","volume":"6","author":"N. Robertson","year":"1985","unstructured":"Robertson, N., Seymour, P.D.: Disjoint paths\u2014a survey. SIAM J. Algebraic Discrete Methods 6, 300\u2013305 (1985)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"9162_CR28","series-title":"London Math. Soc. Lecture Note Ser.","first-page":"153","volume-title":"Surveys in Combinatorics","author":"N. Robertson","year":"1985","unstructured":"Robertson, N., Seymour, P.D.: Graph minors\u2014a survey. In: Surveys in Combinatorics. London Math. Soc. Lecture Note Ser., vol. 103, pp. 153\u2013171. Cambridge Univ. Press, Cambridge (1985)"},{"key":"9162_CR29","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/0095-8956(90)90121-F","volume":"48","author":"N. Robertson","year":"1990","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. VIII. A Kuratowski theorem for general surfaces. J. Comb. Theory Ser. B 48, 255\u2013288 (1990)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9162_CR30","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J. Comb. Theory Ser. B 63, 65\u2013110 (1995)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9162_CR31","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0012-365X(80)90158-2","volume":"29","author":"P.D. Seymour","year":"1980","unstructured":"Seymour, P.D.: Disjoint paths in graphs. Discrete Math. 29, 293\u2013309 (1980)","journal-title":"Discrete Math."},{"key":"9162_CR32","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1145\/322203.322207","volume":"27","author":"Y. Shiloach","year":"1980","unstructured":"Shiloach, Y.: A polynomial solution to the undirected two paths problem. J. Assoc. Comput. Mach. 27, 445\u2013456 (1980)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9162_CR33","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/S0893-9659(97)00027-X","volume":"10","author":"C.R. Subramanian","year":"1997","unstructured":"Subramanian, C.R., Veni Madhavan, C.E.: The existence of homeomorphic subgraphs in chordal graphs. Appl. Math. Lett. 10, 17\u201322 (1997)","journal-title":"Appl. Math. Lett."},{"key":"9162_CR34","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1017\/S0305004100061521","volume":"95","author":"A. Thomason","year":"1984","unstructured":"Thomason, A.: An extremal function for contractions of graphs. Math. Proc. Camb. Philos. Soc. 95, 261\u2013265 (1984)","journal-title":"Math. Proc. Camb. Philos. Soc."},{"key":"9162_CR35","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1016\/j.disc.2005.05.003","volume":"297","author":"G.E. Turner III","year":"2005","unstructured":"Turner III, G.E.: A generalization of Dirac\u2019s theorem: subdivisions of wheels. Discrete Math. 297, 202\u2013205 (2005)","journal-title":"Discrete Math."},{"key":"9162_CR36","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1007\/BF01594196","volume":"114","author":"K. Wagner","year":"1937","unstructured":"Wagner, K.: \u00dcber eine Eigenschaft der ebenen Komplexe. Math. Ann. 114, 570\u2013590 (1937)","journal-title":"Math. Ann."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9162-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9162-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9162-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T20:43:41Z","timestamp":1684183421000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9162-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1,15]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["9162"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9162-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1,15]]}}}