{"entities":{"Q1322004":{"pageid":1332754,"ns":120,"title":"Item:Q1322004","lastrevid":67172955,"modified":"2026-04-12T15:47:01Z","type":"item","id":"Q1322004","labels":{"en":{"language":"en","value":"Paths and metrics in a planar graph with three or more holes. II: Paths"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 562392"}},"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":"Q1322004$6215D25A-13CA-46FD-84B7-154C3A00FF36","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e20cf8b342b8051269e88cd7294cc2f5d27ce366","datavalue":{"value":{"text":"Paths and metrics in a planar graph with three or more holes. II: Paths","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1322004$73639C03-EF5F-4DA7-9200-C22344C9AEDB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"074c3882c537f2c04ad0118b146e4a9a64770f24","datavalue":{"value":"0794.05020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322004$59E8F868-236E-479B-9F5A-66210C38D82E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"14fc360ec3034cf7b4974dd2757eb533d1dfaac7","datavalue":{"value":{"entity-type":"item","numeric-id":423889,"id":"Q423889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322004$4F240654-9887-40A7-AAA7-880C6FEDC0C6","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":"Q1322004$6D2DEF02-D356-482B-9712-F354D77DEED7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"57e9aa89b1f10c36312807a58ccd0e869aeb6e2b","datavalue":{"value":{"time":"+1994-06-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1322004$8028BD9A-9828-4175-B5D6-DF5DBAE1E6AE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"96e6c2081fbb13e5c0efc23d4c2318760f0e9444","datavalue":{"value":"Suppose that \\(G=(VG,EG)\\) is a planar graph embedded in the Euclidean plane, that \\(I\\), \\(J\\), \\(K\\) are three of its faces (holes), that \\(s_ 1,\\dots,s_ r\\), \\(t_ 1,\\dots,t_ r\\) are vertices of \\(G\\) such that each pair \\(\\{s_ i,t_ i\\}\\) belongs to the boundary of some of \\(I\\), \\(J\\), \\(K\\), and that the graph \\((VG,EG\\cup\\{\\{s_ 1,t_ 1\\},\\dots,\\{s_ r,t_ r\\}\\})\\) is Eulerian.   We prove that there exist edge-disjoint paths \\(P_ 1,\\dots,P_ r\\) in \\(G\\) such that each \\(P_ i\\) connects \\(s_ i\\) and \\(t_ i\\) if the obvious necessary conditions with respect to the cuts and the so-called 2,3- metrics are satisfied. In particular, such paths exist if the corresponding (fractional) multicommodity flow problem has a solution. This extends Okamura's theorem on paths in a planar graph with two holes. The proof uses a theorem on a packing of cuts and 2,3-metrics obtained in Part I of the present series of two papers (see the foregoing review). We also exhibit an instance with four holes for which the multicommodity flow problem is solvable but required paths do not exist.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322004$F2822120-B71A-4CB1-B875-F64FE9FCB6DE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322004$28C3A71E-7C71-4C23-A89B-E85DD8064762","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322004$4C449F0B-CB08-4704-A43D-CB2869969ADE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0b223ea518c5f2c305abc414b67bbcd63fc95ea8","datavalue":{"value":"562392","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322004$F737619E-041C-4BF1-943E-B69967D90F72","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2d87a2d2d37c555f2d6e1aeda6f7ce93354cfe73","datavalue":{"value":"holes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322004$BB0FC2D9-6AFC-4DB0-B6B2-C459DB0ABB8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322004$10A2DF6D-60E1-42E5-9201-7D9C2FEFF583","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4db5494d3f7b8f844dd8114683f2cc3cdcc9e9d8","datavalue":{"value":"Euclidean plane","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322004$14C43221-BF7B-4071-9B80-9158203D071D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7832632c39185d9554b5fc9078d102748d811215","datavalue":{"value":"edge-disjoint paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322004$1D29C4A0-CE35-419D-9CBD-5677BD068E53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c51cd2418e1a453fca7a510eacf3309373b3a2f8","datavalue":{"value":"multicommodity flow","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322004$3D4BB44A-0614-4B4A-A6DA-E1ACCE810B07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"093ef3cbea03ec661dc66ae3009ad13581b7249b","datavalue":{"value":"packing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322004$C7AAB0DF-241D-408D-8450-F2B502150961","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":"Q1322004$F40F7A12-897D-4DCD-96CF-5AF74FF26715","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0681e54da74ca9c564f2ab217acf9ea0d21fbd12","datavalue":{"value":"https://doi.org/10.1006/jctb.1994.1002","type":"string"},"datatype":"url"},"type":"statement","id":"Q1322004$345CCC93-FE3B-4BB0-A2F5-9FAEFA821DA4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c97a17795dfc94ce41b1eb74e0b23785dde7ea41","datavalue":{"value":"W2078575982","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322004$7217D4DE-8238-4852-8C58-D274341C0A90","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fff26a0cfb89d32f64ebb24ea95d810370646b4c","datavalue":{"value":"10.1006/JCTB.1994.1002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322004$4A57610B-63F4-4BD1-B3AA-4078A3521423","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b14413bc2b206f960ccbb94a841bafd023ab16f1","datavalue":{"value":{"entity-type":"item","numeric-id":1322003,"id":"Q1322003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a6396aec29893fefc4e7aa5ea578d3c9097e79d","datavalue":{"value":{"amount":"+0.9873567","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322004$CB75E199-DBDD-4CEB-AB4D-F5D98E1A1CFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9606dc4561f35652f612e8acb3be8bb68baeef98","datavalue":{"value":{"entity-type":"item","numeric-id":3129827,"id":"Q3129827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e40acc88dde4502ee2606c22fb4ecabf64153807","datavalue":{"value":{"amount":"+0.8820289","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322004$15F3F5C9-833B-4D3D-869B-C12C2567F515","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4712b5bdb3bb21e885566f257cda3839124bbf5","datavalue":{"value":{"entity-type":"item","numeric-id":2010919,"id":"Q2010919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1dcc5f215b660647716a1fa68c80c1de2d3c8b48","datavalue":{"value":{"amount":"+0.87006706","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322004$F19664CC-4208-427F-911A-506DB7D93AA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54dfba668b9432ce714cbfaddc92e34d6135cce8","datavalue":{"value":{"entity-type":"item","numeric-id":1400805,"id":"Q1400805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b78905d9c93b99cc7d06032babb6bf386e7913f2","datavalue":{"value":{"amount":"+0.86357373","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322004$C0E9724C-30A4-4E57-9AE5-DDB2FF2458F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"503bd4c3f4bde676f01ee0c64b9812f22bd1be2f","datavalue":{"value":{"entity-type":"item","numeric-id":3583303,"id":"Q3583303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a5218dd2a87a253775b17efc8f1ec06ed2afe6d","datavalue":{"value":{"amount":"+0.86233616","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322004$23F70F97-3BFE-4394-A4FA-FA656530DEEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4cb4aed299886406d25f8a737bc7127b8b0f7498","datavalue":{"value":{"entity-type":"item","numeric-id":5903317,"id":"Q5903317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"adcbb51866c860b29257e668ec8c89605609ad5f","datavalue":{"value":{"amount":"+0.8572414","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322004$33AC02DD-ADAA-4562-B6EF-E4ACDED89BF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95c71ce1ce811d5bf76afc3ee640abfc9e6fbc7f","datavalue":{"value":{"entity-type":"item","numeric-id":2851515,"id":"Q2851515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84f7993665e0b6a06d43f36097bbaaf6dd456376","datavalue":{"value":{"amount":"+0.8547946","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322004$808866BE-EA17-41B0-8B75-3DAE9B73FBAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1964ee8c053b792d4099620f26c72c1fb21a078e","datavalue":{"value":{"entity-type":"item","numeric-id":4898144,"id":"Q4898144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a285ecaaafc9c91e5841e5fd1c083d153bf5474","datavalue":{"value":{"amount":"+0.8546069","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322004$A8B743CD-B3EB-42AF-8C65-A8E0A6958CF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37707e828b45cb7df423a386de3af3c209315868","datavalue":{"value":{"entity-type":"item","numeric-id":4783814,"id":"Q4783814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b227405daebd746869da9f1246a0bd6799e0130","datavalue":{"value":{"amount":"+0.8543691","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322004$3B1B98C4-D63F-451E-811C-D7AA29B6519F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c2445923606cceb560e0a2487c2dc70c8df69616","datavalue":{"value":{"entity-type":"item","numeric-id":3754024,"id":"Q3754024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c0a6108d5ff0ed87b4a9bc9eac7db4a5c32cf72","datavalue":{"value":{"amount":"+0.8540549","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322004$A89BFC8C-FD1F-4B32-AF2B-75910A342A5B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Paths and metrics in a planar graph with three or more holes. II: Paths","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Paths_and_metrics_in_a_planar_graph_with_three_or_more_holes._II:_Paths"}}}}}