{"entities":{"Q705742":{"pageid":707591,"ns":120,"title":"Item:Q705742","lastrevid":42652634,"modified":"2025-07-07T17:22:32Z","type":"item","id":"Q705742","labels":{"en":{"language":"en","value":"Cuts, trees and \\(\\ell_1\\)-embeddings of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2133933"}},"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":"Q705742$9F5DBBA7-8E8F-4AB3-A7B6-E4FFFDAC633B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1c8521d101639a8a4ad6c48f610a5dfdda30be7a","datavalue":{"value":{"text":"Cuts, trees and \\(\\ell_1\\)-embeddings of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q705742$839D92E3-B24F-40E1-9023-7353929D1EC9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"74980f10d675ef2a98f734113689d2d9b910a646","datavalue":{"value":"1056.05040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705742$65694C5F-EB11-407D-98E7-3C779BE5A0B6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a4eb02af304dd9babaf8cec1ff7502b920e7cd79","datavalue":{"value":{"entity-type":"item","numeric-id":403673,"id":"Q403673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q705742$D95B3F28-A4DC-42B9-910E-805DBF2CFE1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f43e474a770325110ee7928e67f304b07a143821","datavalue":{"value":{"entity-type":"item","numeric-id":430842,"id":"Q430842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q705742$B101D7CD-7C8B-4666-968F-3B8F760B0554","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e34835133853cddd54ff1d64aa57b1decbcc6ed1","datavalue":{"value":{"entity-type":"item","numeric-id":193720,"id":"Q193720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q705742$32010210-668D-4DE9-ACB0-A23AB3806593","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"098d3ff7023f860d2ad4ff4e99a3417308a6d5f9","datavalue":{"value":{"entity-type":"item","numeric-id":287734,"id":"Q287734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q705742$BA0006C6-C2C3-452B-9652-93AFA61563DF","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":"Q705742$53A706C8-38D4-4735-B983-612E032D7091","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e25cede1ef8d2406793b84eb9dd56b013bc7d13f","datavalue":{"value":{"time":"+2005-02-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q705742$EA2A5168-6B3A-4E08-A8BD-4A951339655A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"97041b12266992bcf6edc7f527e56a94000c6825","datavalue":{"value":"It is investigated when the metric obtained by associating non-negative weights to the edges of a graph can be embedded within constant distortion into an \\(\\ell_1\\)-space. Such an embedding with no distortion, i.e., an isometric embedding, exists if and only if the graph has no \\(K_{2,3}\\) minor. The optimal distortion \\(c_1(G)\\) is equal to the worst possible gap attained by a multicommodity flow problem on \\(G\\). It is conjectured that \\(c_1(G)\\) is bounded for any nontrivial minor-closed family of graphs. If \\(G\\) is series-parallel (or even if it has treewidth 2), then \\(c_1(G)<14\\) and an embedding can be found in polynomial time. Further, \\(c_1(G)=O(\\log \\chi(G))\\) with \\(\\chi(G)\\) the Euler-characteristic of \\(G\\). The embeddings are determined via distributions over cuts and trees, respectively. In the tree case, lower bounds are given, as well.","type":"string"},"datatype":"string"},"type":"statement","id":"Q705742$DF5C6F67-E15C-4A99-8366-A1E04567244F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"826db22c8ad0fdc537525e95eba03f39da931f90","datavalue":{"value":{"entity-type":"item","numeric-id":178041,"id":"Q178041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q705742$C1E47766-E135-4962-B98B-C2A4B0E6C5F2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705742$2567A1FB-2C22-4DF8-8898-9D431E62150E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705742$3DDBE94B-9F7D-40E1-9486-468E8D26C970","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705742$ECAA1399-1FA0-4B80-A5FF-06090A7DCAEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705742$021524E4-6C3C-4510-BA09-7E114C2AA819","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705742$379F99B7-AB89-4B4F-A46B-5845D6127629","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9958cfaa0ee6d6b101caa939a16338de156793a6","datavalue":{"value":"2133933","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705742$2BA413D7-8278-4574-A796-D9960FB0E651","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"861ebea87764fad5ec2c50b374c7c4af05ea1435","datavalue":{"value":"metric on graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q705742$E8789809-DBEB-40A1-8863-8A575F49850F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d0f521aa39ae557111ec88647c9f5f9555860eac","datavalue":{"value":"isometric embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q705742$4BBAD993-22DC-4C53-AC88-812771EC52A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6d9ec77b0669b77734b6831d672122e99e5245c","datavalue":{"value":"minor","type":"string"},"datatype":"string"},"type":"statement","id":"Q705742$5625408F-9B48-43A5-A3BA-37DD3AF63F72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c854bde693a64fa2e101810b01e6f07bb125b5c","datavalue":{"value":"multicommodity flow problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q705742$564A54DD-4743-4503-997F-EE01483EB8B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"534805fa6153b1b3786edcd60407ef0861005e9a","datavalue":{"value":"tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q705742$CC85A308-C31A-4DE6-A086-F143F892AF9D","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":"Q705742$9217130E-CA9A-4E8E-BEEB-39867F2D0B93","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"3125e00e23a29f245b582ffd65c524f3339ac09d","datavalue":{"value":"Q60608702","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705742$BEB57F3E-950B-47D2-A1AE-4CE8018BF264","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"dd2218ee310bf3c7d0853ea589a4fc06b1b5393d","datavalue":{"value":"https://doi.org/10.1007/s00493-004-0015-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q705742$D2DA611E-6B90-4C85-A8FA-C8B5EEC83344","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d393084c400d7babd58128516acb1a3887591f85","datavalue":{"value":"W48861618","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705742$0ABB9B32-FAE2-4ED8-9314-FB7E6191CB35","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4478aa22d789c93f1b7eba1290f9e06985287fc9","datavalue":{"value":"10.1007/S00493-004-0015-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705742$5A36E3F7-1A09-4479-B037-AD879DE7F2BA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b428d97311038a2d1c77244e4a61a2a142ff248b","datavalue":{"value":{"entity-type":"item","numeric-id":2670093,"id":"Q2670093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73f040255da39bca8c27cefaec895de2f9f07207","datavalue":{"value":{"amount":"+0.9167273","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":"Q705742$0A9C11EC-5F9C-4AE0-B12E-DBD2CAD67998","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ced77d62c292ed5b56405a3c4426f6f8300a8239","datavalue":{"value":{"entity-type":"item","numeric-id":291167,"id":"Q291167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52c07fc1d35ff33bbe47dae7e5a2e3b65741b08e","datavalue":{"value":{"amount":"+0.9061574","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":"Q705742$E246842C-0383-45B8-A5F4-67B79B7E8297","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7948905240cb6cf08a05a4dceaf6a00904cbfaff","datavalue":{"value":{"entity-type":"item","numeric-id":4574381,"id":"Q4574381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6018611af50d55d4d6b7cf5fffceb970ff20c472","datavalue":{"value":{"amount":"+0.904153","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":"Q705742$687462C7-02AD-4777-9CB0-5613AFE44C52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f65f1110c0e095586310d3a11a2d26bc62a7a964","datavalue":{"value":{"entity-type":"item","numeric-id":1103631,"id":"Q1103631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0679e610112f8219662d7b0fd2b0792a086c143a","datavalue":{"value":{"amount":"+0.89810145","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":"Q705742$067CE336-6818-4334-904F-0329BBE0FB7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5b7d10ae19ada4584d1696a088a5cc4e0b3d9d0","datavalue":{"value":{"entity-type":"item","numeric-id":2215599,"id":"Q2215599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60aa3c2be1920d2e5b0ba1e1c09bc7c0f46077d7","datavalue":{"value":{"amount":"+0.8911905","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":"Q705742$3F1E6268-A9B8-4681-9DD6-4EE5965E1B0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b68d70ab6450ebe3fc3ba0bcef9981acb5a1699c","datavalue":{"value":{"entity-type":"item","numeric-id":2940093,"id":"Q2940093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6837b44213e31976a95ac717500d519f69821bce","datavalue":{"value":{"amount":"+0.88692045","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":"Q705742$7743A1DC-AA84-406B-A227-BD5401148E76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9eae9f0ec73afc1bded2bacae081001e720af63","datavalue":{"value":{"entity-type":"item","numeric-id":2215853,"id":"Q2215853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df65236103ce65b13bfcd9bbdc8c288f103dd393","datavalue":{"value":{"amount":"+0.8854439","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":"Q705742$3B1F10B8-B86B-43D8-9CAA-D66A5C11EFF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"682d87cc43dfab4572e00bd9dad1016b0aa7975f","datavalue":{"value":{"entity-type":"item","numeric-id":6115369,"id":"Q6115369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2cd0a65f25eb53b634b2dfae9fffdec10edc4eb1","datavalue":{"value":{"amount":"+0.8836144","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":"Q705742$CD81F80C-CD70-4265-9037-8C27243D4E2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4f519b0a7f638d5932524ed3f4867cc267de05f","datavalue":{"value":{"entity-type":"item","numeric-id":5133195,"id":"Q5133195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"237a8384c1b0bb62ea53414b30ea94463e993d2e","datavalue":{"value":{"amount":"+0.88246","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":"Q705742$45F0EF37-1E08-438E-A540-A8B60FF6B4E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c47b9d892f2a83c08a71459a789128ebd08319b1","datavalue":{"value":{"entity-type":"item","numeric-id":4986004,"id":"Q4986004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c0e4d9b462de9800935f38082edfecd55c04db1","datavalue":{"value":{"amount":"+0.8796405","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":"Q705742$DC39AEF7-EDB5-4B0A-9E4D-4E4482E69255","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:705742","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:705742"}}}}}