{"entities":{"Q757396":{"pageid":759245,"ns":120,"title":"Item:Q757396","lastrevid":64107552,"modified":"2026-04-11T17:41:24Z","type":"item","id":"Q757396","labels":{"en":{"language":"en","value":"Decomposition of graphs on surfaces and a homotopic circulation theorem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4191680"}},"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":"Q757396$71388E5D-7961-461A-AAE5-6ECB6562DB3E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"29ded96e038b70322c9a13d51a89aed0aceb66d3","datavalue":{"value":{"text":"Decomposition of graphs on surfaces and a homotopic circulation theorem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q757396$B4723E7E-09B9-40FE-9F5D-BFD897759C46","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b66e09850ba6195516933aa7a999b4aef285215b","datavalue":{"value":"0723.05051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757396$9F082BAB-BF35-4993-A0E5-88AD6FCF6E7F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cb0634acce5d77f4f76fb1e2f43825273f66189f","datavalue":{"value":"10.1016/0095-8956(91)90036-J","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757396$7F01AA2B-EC8B-4F6B-9638-4BAF4798BE6B","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":"Q757396$19D80ACA-AFF3-4272-82C3-492D77259FD2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q757396$D2101AAA-F1AD-4227-8AC5-A4BEDD7C9FFC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0d8b091f1de054cb61840fe438cdf07f166cc3ba","datavalue":{"value":"Let G be an eulerian graph, imbedded in a compact orientable surface s, with D a closed curve in S. Let mincr(G,D) denote the minimum number of crossings of G and \\(\\tilde D,\\) among all closed curves \\(\\tilde D\\) homotopic to D and not meeting V(G). Let mincr(C,D) denote the minimum number of crossings of \\(\\tilde C\\) and \\(\\tilde D,\\) among all closed curves \\(\\tilde C\\) and \\(\\tilde D\\) homotopic to C and D, respectively. Then it is shown that E(G) can be decomposed into cycles \\(C_ 1,...,C_ t\\) so that for each closed curve D in S, \\(\\min cr(G,D)=\\sum^{t}_{i=1}\\min cr(C_ i,D).\\) The following ``homotopic circulation theorem'', which applies to a problem involving automatic design of integrated circuits posed by K. Mehlhorn, is derived as a corollary: Let G be imbedded in S, with c: E(G)\\(\\to Q_+\\) a ``capacity'' function; let \\(C_ 1,...,C_ k\\) be cycles in G, with \\(d_ 1,...,d_ k\\in Q_+\\) the corresponding ``demands''. Then there exist circulations \\(x_ 1,...,x_ k\\) in G such that each \\(x_ i\\) decomposes fractionally into \\(d_ i\\) cycles homotopic to \\(C_ i\\) (1\\(\\leq i\\leq k)\\) and such that the total flow through \\(e\\in E(G)\\) is \\(\\leq c(e)\\), for all such e, if and only if: for each closed curve D in S not meeting V(G), the sum of the capacities of the edges intersected by D (counting multiplicities) is at least \\(\\sum^{k}_{i=1}d_ i\\cdot \\min cr(C_ i,D)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q757396$8C8D98FC-2D61-4A30-9A9E-C5818A6B5BF3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"205b6d05d63e09819854956633396177079e7ebb","datavalue":{"value":{"entity-type":"item","numeric-id":591987,"id":"Q591987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757396$DC6D4E59-D341-409F-B1D4-A00CFBC2ED6F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757396$F8D7416A-9D8F-43E5-A605-0ED433680FE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757396$8B274B65-30E9-48D1-843F-4C5ACC305D91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757396$A54F6F29-ECEB-43BB-9107-5109605072D4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"93f4f63007d5dbff7f37c2c3d434eddc50a41507","datavalue":{"value":"4191680","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757396$DA20953D-DB90-49C4-8F1D-C1090BF17AD4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f53514353c32096d2360d851b885df29c299b68","datavalue":{"value":"eulerian graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q757396$67686241-8CD3-4ECA-9706-48D1FC1A22BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8dbb9b9139109c8c727c65caedc300526ac0bcf6","datavalue":{"value":"compact orientable surface","type":"string"},"datatype":"string"},"type":"statement","id":"Q757396$63C45036-B967-4E3D-9A07-89CC17FD9215","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6773a8681cb308e3c85a2fe4938dfb20fb23f96a","datavalue":{"value":"number of crossings","type":"string"},"datatype":"string"},"type":"statement","id":"Q757396$4E563C46-F2A1-4492-91EE-E08EDD4EA204","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":"Q757396$7080843C-3652-467D-B006-7B8DFCD99D06","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"47aa619ccf37b3ec87c764cf34b1641d4bad3a75","datavalue":{"value":{"entity-type":"item","numeric-id":5593095,"id":"Q5593095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757396$0E005F8C-B0B4-4778-8764-0A126F260854","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18d109e02a8787c377a3e5362b7b018330dc59c5","datavalue":{"value":{"entity-type":"item","numeric-id":1210581,"id":"Q1210581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757396$38F063B4-84FF-46B6-85B1-5EAE5D1806A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd9dee699be841e77e080299abd42ea8d7c41342","datavalue":{"value":{"entity-type":"item","numeric-id":5640451,"id":"Q5640451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757396$5053BB37-A2CC-4E83-90A9-6D770CDC9741","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b205f454d701594d167ca091e80b0f1322f39f7","datavalue":{"value":{"entity-type":"item","numeric-id":1097900,"id":"Q1097900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757396$F0A2F919-C537-44F2-BDB6-DCB8BBF60C02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2f7d2d790230ee2feb8970801b994c37debfbc5","datavalue":{"value":{"entity-type":"item","numeric-id":3777475,"id":"Q3777475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757396$7E9BE7C7-A9C8-432F-9923-9AC1F0D75093","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce56514a43df509173b28d74ff00cdce0342e274","datavalue":{"value":{"entity-type":"item","numeric-id":1255022,"id":"Q1255022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757396$14AB9BB3-3221-45A6-BF9D-EFF7F5476F66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ead9bfd2cc4f98020277896af0e5eaa4f16e3e24","datavalue":{"value":{"entity-type":"item","numeric-id":2521173,"id":"Q2521173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757396$DE2E4DC4-F888-4FC0-ACEE-082B8E1FF663","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc8d0e8b5957bb46d6c54c5df5f602ad7968742e","datavalue":{"value":{"entity-type":"item","numeric-id":5534009,"id":"Q5534009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757396$8DDA9930-1DB8-4E95-A80D-7C5A96516C81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32a7de3806dff935793f999271e8c8c446568af9","datavalue":{"value":{"entity-type":"item","numeric-id":4119824,"id":"Q4119824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757396$FD2948B2-673F-4256-B1AF-2F6E502166CB","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":"Q757396$6AEEB7BC-D0EA-44E2-BB4A-4ECD08E2E74F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5792aa3f5f6a3dc2fb552746c691c142eb682973","datavalue":{"value":{"entity-type":"item","numeric-id":5536127,"id":"Q5536127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757396$D326E017-B8A6-4533-88E7-11CD056BCAF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56c6c299e15ddeb001671e573dc9a5439e5a86a0","datavalue":{"value":{"entity-type":"item","numeric-id":3818127,"id":"Q3818127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757396$EB80C600-C679-42E1-B7D7-BC86E8C49E85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e78fa8bfb615b81ec94a1f433a7f800298975fe1","datavalue":{"value":{"entity-type":"item","numeric-id":3351373,"id":"Q3351373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757396$10E92128-C1FD-4864-B31B-0B7B1B314146","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c83edb47336ade6becc57b74a0cff96e4850ba11","datavalue":{"value":{"entity-type":"item","numeric-id":1120584,"id":"Q1120584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757396$ED446545-0700-4C1A-B827-1276427BAEE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5b1e6e5b0508eada9eca5832a4c7d9504af1ba0","datavalue":{"value":{"entity-type":"item","numeric-id":1210587,"id":"Q1210587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757396$A5119010-00B7-4CFB-9C17-FD6D39E3A02F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a9cf72cc45394583788e11f6a93595103c05969","datavalue":{"value":{"entity-type":"item","numeric-id":757395,"id":"Q757395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757396$044CCD6B-2432-4552-8B93-3C38B7DC135D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5b88621364755942be76b6c69b121a893b8c5fd4","datavalue":{"value":"https://doi.org/10.1016/0095-8956(91)90036-j","type":"string"},"datatype":"url"},"type":"statement","id":"Q757396$E857525F-39BA-4E1F-B316-06A48C41D680","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d50c6cc5c123bfa9e2fa415f3ffabf788ffba12c","datavalue":{"value":"W2021542269","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757396$3BFC0320-22CF-4FB2-B3A8-C78AC978F46C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2dbf8d5cbd9ece6bead4e0fa5d545881c7f63f46","datavalue":{"value":{"entity-type":"item","numeric-id":6481473,"id":"Q6481473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757396$325C0D7B-7DBC-4213-9C62-A55E4042F629","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f078e14869d5b77364b2e6aacbde924106a3443e","datavalue":{"value":{"entity-type":"item","numeric-id":1369657,"id":"Q1369657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d37f5991d4695b93a188fe64dda30f2c510f1abb","datavalue":{"value":{"amount":"+0.9107847809791564","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":"Q757396$43E4F71B-225C-4C63-923A-0289ADEC28AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a90eb46cb57c6939ad8f7fbbb20d3d6ea050810","datavalue":{"value":{"entity-type":"item","numeric-id":757395,"id":"Q757395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"042deb66142898df3bea48896063b57e45219762","datavalue":{"value":{"amount":"+0.7942181825637817","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":"Q757396$B914A7DE-C75B-49E8-A6BE-A69B5FB40888","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06077973187bc8d30f0b8ec8abceb4eb5ff49b03","datavalue":{"value":{"entity-type":"item","numeric-id":4280138,"id":"Q4280138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cec64723ff6970a26cfb8403f1ce21c254b76b93","datavalue":{"value":{"amount":"+0.7881945967674255","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":"Q757396$21070997-B05D-4628-BEF9-5F14C654D5B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d78950d352c036939bcef3f25434f34d556db0bc","datavalue":{"value":{"entity-type":"item","numeric-id":1814589,"id":"Q1814589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5a7e9bffe02355f9cba09f528cc58f34129362a","datavalue":{"value":{"amount":"+0.785789430141449","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":"Q757396$0C54818C-BA5F-471E-87C1-63B355862FA2","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":"fbdc044ddc4599de43f7cfe7fd27c67b8d0442b8","datavalue":{"value":{"amount":"+0.7801398634910583","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":"Q757396$DC65C7C1-0C9F-4C62-8CB4-C6B1AAEBC10C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Decomposition of graphs on surfaces and a homotopic circulation theorem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Decomposition_of_graphs_on_surfaces_and_a_homotopic_circulation_theorem"}}}}}