{"entities":{"Q1069956":{"pageid":1080708,"ns":120,"title":"Item:Q1069956","lastrevid":66212547,"modified":"2026-04-12T08:18:07Z","type":"item","id":"Q1069956","labels":{"en":{"language":"en","value":"Edge-disjoint paths in planar graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3933110"}},"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":"Q1069956$750EB307-EE7C-4134-BC32-8AF758334A17","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"59a3496132a6f644de18065dbf0cb04fdbaf8e85","datavalue":{"value":{"text":"Edge-disjoint paths in planar graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1069956$F2A1A4F9-9119-4614-8EDA-8A7018B1F080","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bdc7510ee4aebcc236e777d8d6cf55183552be56","datavalue":{"value":"0583.05036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069956$24F43F19-C308-4806-899D-F6C97508979E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"58ec71738a830ea7dea184254b5082032fd3cb3c","datavalue":{"value":"10.1016/0095-8956(85)90046-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069956$EBCEA029-9439-4545-85D0-2AFD506B2184","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c0fc15a7e3d4421bc64b9f2f3b3f0c93d5e0ce58","datavalue":{"value":{"entity-type":"item","numeric-id":226797,"id":"Q226797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069956$C5ED1FDA-9149-490D-A420-FCD4B955E524","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":"Q1069956$947B352A-5E42-41C8-8F15-865E9B0CBE48","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1069956$EF1D8358-D3FF-4ED8-9FA6-E790E8758974","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"98f12db07b9aef1e67f7d9568146108d025193f5","datavalue":{"value":"The following problem is considered. Given a planar graph G, find k edge- disjoint paths in G connecting k pairs of terminals specified on the outer face of G. A necessary and sufficient condition for the existence of such a collection of paths is given in the case when each node of G not on the outer face has even degree. This generalizes earlier results on \\textit{H. Okamura} and \\textit{P. D. Seymour} [J. Comb. Theory, Ser. B 31, 75-81 (1981; Zbl 0465.90029)] and the author [Combinatorica 2, 361-371 (1982; Zbl 0515.05044)]. The proof gives rise to a polynomial algorithm for solving the above problem. In particular, the integral multicommodity flow problem belongs to class P when the underlying graph is outerplanar.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069956$6EBF6C84-7F10-4CA6-85BC-E7F253AFD1CF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069956$C5234980-3573-4616-BF85-A8DBBBAF9454","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069956$EDD5C830-46F6-4312-A3DC-97B6AB371786","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069956$A4BC5C51-F90C-4EDC-8425-5E98E3DF7B7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069956$ADD6C7B5-3E62-4FD6-9656-31B03156CF42","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3be32afca3f7d2eafb1d99f16eb6f17394339b0c","datavalue":{"value":"3933110","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069956$20EF45A3-E8BE-4A23-B0D2-6FCA8FCD5F2E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d606522db403f40c4cce458d8ce8069e0c3f77c","datavalue":{"value":"edge-disjoint path problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069956$9C5A2111-3DE0-4328-89D6-38BAB7DCD34E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069956$3FBB7144-894F-4103-A305-0E8A22CD01E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069956$EA22689D-0821-4A7C-85DB-1D3232D20D1D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"90c78b3265eaf03d2c9093f31b0f9730424156f8","datavalue":{"value":{"entity-type":"item","numeric-id":175610,"id":"Q175610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069956$439F9948-16D7-467F-8390-467E104172AC","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":"Q1069956$B92730C8-60DE-4076-A6A5-B2BCF7A8BB05","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"090fa1ff8618331e9c246739e73a4aaae8b8bc41","datavalue":{"value":"https://doi.org/10.1016/0095-8956(85)90046-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1069956$3FB4ACDC-DCDB-4ADB-9C92-5E28CE107617","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"dc06eb86f32aae426c8dcb6432e451f1e6e8d91f","datavalue":{"value":"W2012969943","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069956$DC23A26B-68C8-48B7-A383-E460472C1808","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6017654ae19542c8121474ad15793fe66ea1c8ff","datavalue":{"value":{"entity-type":"item","numeric-id":1051655,"id":"Q1051655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069956$ED1B80C1-DD81-4767-A461-D5BA07BBC8BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6f73a3ac055f5eb58afc4d9dc23d52069f8d7a2","datavalue":{"value":{"entity-type":"item","numeric-id":3968457,"id":"Q3968457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069956$7CD9CBEB-0A25-49A4-9732-373588CB286B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e815776bae2945bdede9d1abf01ab280b93b87c","datavalue":{"value":{"entity-type":"item","numeric-id":1154916,"id":"Q1154916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069956$2C2CAAAD-7044-4E60-942F-FB6709358992","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f86069b80a66f03da1cb27c5fa9c269c7c7bfc3","datavalue":{"value":{"entity-type":"item","numeric-id":3330973,"id":"Q3330973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069956$9D914A21-F027-4888-8148-F96E6CC0733F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6d835ccc7da104c96eb1a22d7d8e47a280dbf09","datavalue":{"value":{"entity-type":"item","numeric-id":1150632,"id":"Q1150632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069956$6D560FC3-D1A5-4432-B6B8-E9D5E3160682","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"91a8a92ba35c4b35ad666b6243007947ecb459ec","datavalue":{"value":{"entity-type":"item","numeric-id":3893626,"id":"Q3893626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069956$0AFCF419-BDC5-4F54-A8E7-B21FEFF329AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"463f0cac3e60d82d492cd248d7fbeefa8310d26f","datavalue":{"value":{"entity-type":"item","numeric-id":1150633,"id":"Q1150633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069956$B38E0FA9-1FEC-4D91-B586-C8BF57D0B377","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1ffa1866f7fa8225c5c4097656e297e6927fbfc","datavalue":{"value":{"entity-type":"item","numeric-id":809091,"id":"Q809091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"269fedc7837d54ababac2d0bac2fac659f8ab2a0","datavalue":{"value":{"amount":"+0.8981578946113586","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":"Q1069956$E87745D0-A256-4D40-A4C0-BD513F956C26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43bb7172da589c90f524fbb14f9e47478ba11a19","datavalue":{"value":{"entity-type":"item","numeric-id":1842575,"id":"Q1842575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24ca495e99f8b76f4f0998bd287a3eaa9f56bab2","datavalue":{"value":{"amount":"+0.8909631967544556","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":"Q1069956$06A8D5B7-449E-4FEA-9E29-CFF9B18BA17B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4977730f092ab66be71a6750e73f5fc0033f1ad0","datavalue":{"value":{"entity-type":"item","numeric-id":2367446,"id":"Q2367446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d17368b9ba8a8d7ca6409b951bc1e58109f3a337","datavalue":{"value":{"amount":"+0.8741838335990906","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":"Q1069956$F454197A-E497-44D0-BACF-820654182CD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3083edbddcf697f0c0a9be22e39a8ca46843ab8f","datavalue":{"value":{"entity-type":"item","numeric-id":1097900,"id":"Q1097900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71c8a5a4251bea8566ea894e61572d83e67c6159","datavalue":{"value":{"amount":"+0.8739625811576843","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":"Q1069956$E2CE94E1-0E7F-4854-AC62-B7CF62909B04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e44fb6c1371a94b0f1c334e029e2d6dc40956698","datavalue":{"value":{"entity-type":"item","numeric-id":3439308,"id":"Q3439308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e43b8e2fa113f6fc9d186290ccaa17be37ea7290","datavalue":{"value":{"amount":"+0.8722479343414307","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":"Q1069956$3633D3BE-996F-485D-8DA3-ED7989A4DE0A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Edge-disjoint paths in planar graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Edge-disjoint_paths_in_planar_graphs"}}}}}