{"entities":{"Q809091":{"pageid":810939,"ns":120,"title":"Item:Q809091","lastrevid":64534374,"modified":"2026-04-11T20:32:04Z","type":"item","id":"Q809091","labels":{"en":{"language":"en","value":"Packing paths in planar graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4210172"}},"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":"Q809091$8775CDB9-9382-4248-97DC-7B70ECE2AC21","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d55262296c5a951e4d4e48f26e8f60007a785182","datavalue":{"value":{"text":"Packing paths in planar graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q809091$E932495D-5B47-4216-9E63-B63FE6F6970D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ea8dd9e952c052d2b5692f8262b77ab16ecdd51f","datavalue":{"value":"0732.05032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809091$FD6247D8-625D-42D3-8F53-75A80299EF6D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e119a0f8dfe4195391cabc3a921a3b5ae2e32412","datavalue":{"value":"10.1007/BF02128668","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809091$243E1EFE-359B-4FE7-A009-3A42E35A9652","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":"Q809091$C24BA069-A0AE-49AF-86EC-BF70E95669ED","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809091$9DDECE4F-FFA0-4386-8421-5685F3DA5C15","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q809091$4445AA1C-087E-42D6-817E-6FB5B3D4C226","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"987dec95c85716bbf37fc63c182b4920ef420b1f","datavalue":{"value":"In a graph \\(G=(V,E)\\), k pairs of nodes \\((s_ i,t_ i)\\) \\((i=1,...,k)\\) are given. The edge-disjoint paths problem is to find k pairwise edge- disjoint paths joining the corresponding pairs \\((s_ i,t_ i)\\). Suppose we designate by H the graph with vertex set V and edge set \\(\\{s_ it_ i:\\) \\(i=1,...,k\\}\\). The above problem is NP-complete even when H just consists of two sets of parallel edges. For the special case when \\(G+H\\) is planar and H consists of two sets of parallel edges, P. D. Seymour gave a result. This paper generalizes Seymour's theorem: When \\(G+H\\) is planar and the edges of H are on at most two faces of G, the edge- disjoint paths problem has a solution if and only if certain two criteria on cut edges hold.","type":"string"},"datatype":"string"},"type":"statement","id":"Q809091$708D5648-A66F-49F2-91F4-B01A7089C8C7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809091$6FAB2D57-9870-4DEF-BD72-8A1876EC5B8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809091$43C2DE09-9073-4A6A-B082-9B2349872220","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809091$4A37C157-7F5B-44C4-A84A-D41A0E19E9D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809091$F8B8E03D-B3E9-441E-B17A-538A956539E6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"edf94f5e3e1ee26742319671874387ea083931be","datavalue":{"value":"4210172","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809091$88604973-E1D2-41D3-AB33-7E47701E7537","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7832632c39185d9554b5fc9078d102748d811215","datavalue":{"value":"edge-disjoint paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q809091$1F96DFDF-6474-4EFC-A341-CDEF12DFC8F7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bf8837edd6f8e1022b15c3d0748921656854f53e","datavalue":{"value":{"entity-type":"item","numeric-id":1811077,"id":"Q1811077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809091$E8B68498-EBD7-45E3-B1C3-E85CFB0EF408","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":"Q809091$17BF3EE6-94D4-46DC-8182-4AF7E44A7202","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"55223ae6f91a9a3c0f6a3be0cfb6236eaf5fcb6a","datavalue":{"value":{"entity-type":"item","numeric-id":4132234,"id":"Q4132234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809091$6ACAE32D-44EE-4E1A-BDCF-D3C13A0B4F96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6006ebe87aff4756f95955d2465a794f45cfda62","datavalue":{"value":{"entity-type":"item","numeric-id":585080,"id":"Q585080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809091$B418AD1A-A879-4B13-B2D5-870C5CA746AA","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":"Q809091$4E0639ED-7815-4DD6-A0C1-A92C0B41D5F7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"02965795d4915f3637bf77dba4812c466dd7e50d","datavalue":{"value":"https://doi.org/10.1007/bf02128668","type":"string"},"datatype":"url"},"type":"statement","id":"Q809091$65A9813C-8325-4552-8E5E-9424B9FBBC42","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"71e0f9c288122a68373a222c9e4bda64e6f39976","datavalue":{"value":"W1966166008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809091$BF7DA357-0D05-4EFF-B0B0-A391B301F84A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c1a368896971d18db80372391586023d783166c","datavalue":{"value":{"entity-type":"item","numeric-id":1906072,"id":"Q1906072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e231173e128f4e97e401c283e3c8a236e00e11b","datavalue":{"value":{"amount":"+0.91523015499115","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":"Q809091$E7558B93-D2ED-46C5-857B-03BE73AFDE4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7603a3f6f2893906bde0c9a7f58cd014e60bf6e","datavalue":{"value":{"entity-type":"item","numeric-id":3972951,"id":"Q3972951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e231173e128f4e97e401c283e3c8a236e00e11b","datavalue":{"value":{"amount":"+0.91523015499115","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":"Q809091$05698170-171E-43C6-A89C-6575A395B3BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b21bc0082bf72bedcfc8f03836d67e2964cfc7bc","datavalue":{"value":{"entity-type":"item","numeric-id":1069956,"id":"Q1069956"},"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":"Q809091$34A31CBC-3AB5-4183-94AD-CC9A7026F2ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3794e2aa554b553087030530b298006877b8ee98","datavalue":{"value":{"entity-type":"item","numeric-id":3211338,"id":"Q3211338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"335f8bf9a56aa406d5c0b5e480dca2170f2c625a","datavalue":{"value":{"amount":"+0.8763562440872192","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":"Q809091$468C3E70-FE95-4682-80CB-3B3F916A1053","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":"32dceebbc5441a0332bcc4cfc4a5120556fa69fb","datavalue":{"value":{"amount":"+0.8748016953468323","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":"Q809091$15CEA5BB-BE33-47C0-A479-82CDA5FD1961","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Packing paths in planar graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Packing_paths_in_planar_graphs"}}}}}