{"entities":{"Q1111568":{"pageid":1122317,"ns":120,"title":"Item:Q1111568","lastrevid":69668907,"modified":"2026-04-13T08:35:12Z","type":"item","id":"Q1111568","labels":{"en":{"language":"en","value":"Graph minors. VII: Disjoint paths on a surface"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4075108"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111568$B1A7B8E0-FB02-4410-A385-966BEDE2ABC6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c594828052a97428a0d799ff4d3364cfcb2add02","datavalue":{"value":{"text":"Graph minors. VII: Disjoint paths on a surface","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1111568$2195953D-3B3E-491D-AFD4-7E4D54D752BB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b7de7e45f748c3cf05dde2af4903a86801a48a72","datavalue":{"value":"0658.05044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111568$0358C6AF-D6D4-470C-92D0-FF5DD56795F7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3bf50a8662d7280a67b04d5c96484f8875571a80","datavalue":{"value":"10.1016/0095-8956(88)90070-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111568$2BA3B2AF-3EF8-47F8-A289-DA797BABFB49","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fdbfdb659d9aeba37340367b24592700a75b41ee","datavalue":{"value":{"entity-type":"item","numeric-id":175487,"id":"Q175487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111568$C891C13C-DBE1-452A-9208-36239F9E6B01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b7666b1aea36d852e5d73efdf8f9faa64e3f54f","datavalue":{"value":{"entity-type":"item","numeric-id":705887,"id":"Q705887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111568$AD66CF73-D00E-4DCF-B1D9-38AFBE551CE4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111568$FCEA0ACF-90AB-4709-85D0-2BDA30C69798","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1111568$20CB382C-335F-4522-9ACC-5C1695165098","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"20656f8eac7d97fb8ed9b87158ab3fd31230bdd7","datavalue":{"value":"[For part VI see ibid. 41, 115-138 (1986; Zbl 0598.05042).]    Continuing their series of nonconstructive proofs of polynomial solvability of problems, the authors here address the following ``homoplasty problem''.    Let \\(\\Sigma\\) be a compact surface, eventually with boundary. Two graphs in \\(\\Sigma\\) are homoplastic iff there exists a homeomorphism of \\(\\Sigma\\), leaving its boundary invariant, and transforming one into a graph which is pathwise homotopic to the other. The ``homoplasty problem'' is to decide whether for given graph G and forest H in \\(\\Sigma\\) there exists a subgraph of G homoplastic to H.    After proving several sufficient conditions for the homoplasty property to hold, mainly by way of geometric topology techniques, it is shown how these may be used to obtain a polynomial decision algorithm for the homoplasty problem for fixed surface \\(\\Sigma\\) and forest H in \\(\\Sigma\\). It then follows that for any surface \\(\\Sigma\\) and integer k the following disjoint connecting paths problem is polynomially solvable: given a graph G in \\(\\Sigma\\) and k pairs of vertices s(sub i), t(sub i) (1\\(\\leq i\\leq k)\\) of G, decide whether there exist k vertex-disjoint paths of G linking each of these pairs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111568$62022414-CE47-48E5-AD76-DBC2A762006D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111568$EC1A1474-8A56-492D-B9FE-86DB6C3BF428","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111568$77025D3C-5593-4D46-87D3-DB302316431A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111568$A5E0D9DB-2CEE-43EE-85E7-7E62FB817560","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111568$803A3CE3-45D4-4416-BDAF-47580467E553","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8324171814577cc27c53cb554895537c5d8d0bee","datavalue":{"value":"4075108","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111568$883F9EDA-712D-4482-B5D2-DFC7AB444821","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"089ec02d70289b9fe6b01ed4a60defe3dc19e369","datavalue":{"value":"graphs on surfaces","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111568$C64E1AE0-7CC5-46EB-8F15-984B6138E8E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"577c070866bfc3759b53cf2111a310601b48b9df","datavalue":{"value":"compact surface","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111568$C30A9857-8213-4C36-BBC8-77F4A55FF54C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc79eafc1d9ceb1ab79797a36449e9df369395df","datavalue":{"value":"forest","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111568$796B46DB-75B0-4DD8-BD16-657D067F45A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac52a6dae9112afc253301018b51576b91a3d9a1","datavalue":{"value":"homoplasty","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111568$207DC0B5-BF46-4EBC-BF88-0278D9D5209F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6adce81296e429a8f0c4650523fed5eb44816f3","datavalue":{"value":"disjoint connecting paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111568$77C69180-A79C-4C08-9485-048D52387BB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be50188cd81901fea93b228767aac63b28c3f1cf","datavalue":{"value":"vertex-disjoint paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111568$7A9E4F71-63BA-4FE9-9052-186713E93F18","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5e09f3da1a7483864918926ab5885138a8f45aaa","datavalue":{"value":{"entity-type":"item","numeric-id":166210,"id":"Q166210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111568$B4FF82B7-6928-4471-80AD-8C33113F198E","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111568$19CC638B-CF4D-4E04-8E1D-9DB167A7416B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"edaa3febb27e4cd2abfd93a146693b2e52f79173","datavalue":{"value":"https://doi.org/10.1016/0095-8956(88)90070-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1111568$0CEC599F-E156-462D-84A8-C72566108944","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"21eef6f1eb2816f84d2b85586603d462864e2bb1","datavalue":{"value":"W2003311624","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111568$D5E32BB5-D944-48AF-8184-DC5EF8FEBF91","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"08213a80fab0ff1ea73797a8e884cdce56d01c18","datavalue":{"value":{"entity-type":"item","numeric-id":3883164,"id":"Q3883164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111568$86F8830F-C141-4F37-8508-D06DD0F27D33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58b714d35fe19a74cb4855dff5bf91ce5065aaa2","datavalue":{"value":{"entity-type":"item","numeric-id":5727288,"id":"Q5727288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111568$F4C82ED3-3405-479B-B1FB-841A342316B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ef0f89b3d4848285d16b9f024f89d4a5e76a218","datavalue":{"value":{"entity-type":"item","numeric-id":799684,"id":"Q799684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111568$B0020BEF-38A4-4BD4-8BEC-E7E0DA4CADDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9cd5ab2b4dcc204e3d6bd923419ed31e399a96a","datavalue":{"value":{"entity-type":"item","numeric-id":1079580,"id":"Q1079580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111568$0B26FC39-2331-4EC5-901D-78C8A553C49E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5148d9be9353afd8f71a6e46eb754f015cf333e1","datavalue":{"value":{"entity-type":"item","numeric-id":2639870,"id":"Q2639870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111568$044CC020-DAFD-41B4-A098-C8AB5B2E814C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"398ef8bc27e00efd8312d46a33efaa0333728c17","datavalue":{"value":{"entity-type":"item","numeric-id":1892832,"id":"Q1892832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111568$B99CEDF0-ADBD-499F-A700-5B30469D811D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47ad1d03b0c13170d17091dfbe9d9ece435538fa","datavalue":{"value":{"entity-type":"item","numeric-id":3886473,"id":"Q3886473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111568$6C576A37-2D89-44AF-8537-6A3C1BE1560C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"172d3d8dcff5644feb470680a43687276d8101d0","datavalue":{"value":{"entity-type":"item","numeric-id":1079580,"id":"Q1079580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a81dd88d8fab7e3da05f2e001dcdbe8a2696ef1","datavalue":{"value":{"amount":"+0.8785499930381775","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111568$B96B5AE1-6FE7-48C0-8B6E-1B7C9347E239","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b6f90606216f21b6a05b7eefdd5ba4d7a36b6fc4","datavalue":{"value":{"entity-type":"item","numeric-id":3679228,"id":"Q3679228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbab60980d7e4a678c1a1e451d304d64465d8909","datavalue":{"value":{"amount":"+0.8534783720970154","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111568$AF2D5EBF-4B68-42DC-846F-ECA8884E3EE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbb7fc699ba6cba99d0b5f2b785c583cc7ab79c2","datavalue":{"value":{"entity-type":"item","numeric-id":1892832,"id":"Q1892832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2b7502a4d1e333c1be99249379ce05b4a6804af","datavalue":{"value":{"amount":"+0.8533056974411011","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111568$C27057E2-814C-4198-AD5A-292769752319","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"127006cddd28add3bfb10592741f8379d5f470d9","datavalue":{"value":{"entity-type":"item","numeric-id":1179127,"id":"Q1179127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"805de4963d25b4f6e30c015d4967da6a49f28824","datavalue":{"value":{"amount":"+0.8489652276039124","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111568$891F3D5E-A9E5-4396-A5F7-15949F73DC7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d43087982e5c28fd34f1abd9aa65ce98aa588f8","datavalue":{"value":{"entity-type":"item","numeric-id":4324341,"id":"Q4324341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f758fb2426d885b90a48baf739b1d59f5fda8993","datavalue":{"value":{"amount":"+0.841212272644043","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111568$F1B64E4A-9D09-4011-AE0B-3E8AF7C45724","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Graph minors. VII: Disjoint paths on a surface","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Graph_minors._VII:_Disjoint_paths_on_a_surface"}}}}}