{"entities":{"Q2052722":{"pageid":2063464,"ns":120,"title":"Item:Q2052722","lastrevid":57701127,"modified":"2026-03-31T23:40:36Z","type":"item","id":"Q2052722","labels":{"en":{"language":"en","value":"The Reeb graph edit distance is universal"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7434420"}},"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":"Q2052722$C41190C0-28AC-43E0-ACE0-2655F9E9A4C8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7357022229fc4f628deac5ba12891444f3b3b697","datavalue":{"value":{"text":"The Reeb graph edit distance is universal","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2052722$EE1B8602-3F12-4958-AC7B-7FC60C6185C6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d4a22115c97e8efd73c4cf1055cf02ea00cbe898","datavalue":{"value":"1485.55006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2052722$EE7DC289-E440-40A1-8AF8-441E2FB20683","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"44d808cd5ad7884159617d1e32b0de195f2ae8a8","datavalue":{"value":{"entity-type":"item","numeric-id":133719,"id":"Q133719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2052722$E3A97359-5A40-4923-9062-1633E9D5F3AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b505ec727cc6e5dee6fb140d25b88804343dee8","datavalue":{"value":{"entity-type":"item","numeric-id":230633,"id":"Q230633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2052722$970B1F3F-0FF1-4055-BCBA-B2388230D93E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"70bf32eee209ea3d977a19f6fb54e9d18c20dfa6","datavalue":{"value":{"entity-type":"item","numeric-id":162254,"id":"Q162254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2052722$760F8C1F-D58C-4966-81A0-969F77AFCE09","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1de0dee9456ae54727642f6ba64e62fe6eaa93c2","datavalue":{"value":{"entity-type":"item","numeric-id":203859,"id":"Q203859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2052722$0FA36CCC-EE0C-479D-B227-8F7A8B9EB2FC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e478ee1306f12b3efcf9d93fcafb155f884767e4","datavalue":{"value":{"time":"+2021-11-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2052722$4A1458D0-9158-485E-8FCC-78F47EBADAEF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"606cd76931ca4f3eed3f81ef92ff24df61eae972","datavalue":{"value":"https://arxiv.org/abs/1801.01866","type":"string"},"datatype":"url"},"type":"statement","id":"Q2052722$B5A96686-9099-412F-A3EF-A8F84E0F6761","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"50d917b714c3311c8296fd78568a3eacf300a46f","datavalue":{"value":"For a Morse function $f: X\\to \\mathbb R$ on a compact smooth manifold, the Reeb graph of $f$ is the quotient space $X/\\sim_f$, with $x\\sim_f$ $y$ iff $x$ and $y$ belong to the same connected component of some level set $f^{-1}(t)$ for some real number $t$. It is proved in Proposition 2 that any Reeb graph of a PL (piece-wise linear) function is a finite topological graph.  In Section 3, the authors define some pseudo-metrics on the collection of the Reeb graphs for all the Morse functions (or PL functions) on a fixed space $X$. The authors define the universal properties of a pseudo-metric. They construct a distance $d_U$ and prove that it is universal in Proposition 5. They prove that $d_U$ is intrinsic in Proposition 6 and state that whether $d_U$ is a geodesic metric is unknown. They also review and re-introduce the functional distortion distance and the interleaving distance and claim that these two distances are stable but not universal. Finally, they give some lower bounds.  In Section 4, the authors introduce a new distance, the edit distance $d_e$. They prove that $d_e$ is stable and universal.  In Section 5, the authors further explore the edit distance of Reeb graphs $d_{eGraph}$ as well as its stability and universality.  In Section 6, the authors discuss the motivation of the study of $d_U$, $d_e$, and $d_{eGraph}$ in topological data analysis, the relations between these distances and graph zigzagging, and some further questions which are of interest and could motivate further research.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2052722$089DEB39-A52B-4180-BC4B-AE2DCCC67AD5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"de0ce84ba85dbb6f414d6206a5b3716bbe996dcf","datavalue":{"value":{"entity-type":"item","numeric-id":776638,"id":"Q776638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2052722$6B178B44-BAD0-44AA-BB46-E6989B25CAD3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d11b3bc2c49f44a4523c75be063212b487602a90","datavalue":{"value":"55N31","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2052722$FB30DB25-7DC5-4AAC-A7A3-3A9E987B41E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2052722$E1D131EB-1F2B-4B3E-B240-AF53B14EE2E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9934057d10323980704e6b94db4ebac54a6fd5ff","datavalue":{"value":"54E35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2052722$33E873C7-AD19-459E-B28E-8ADDC0F9465E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"920c4d6d4b4bbb19ce691e589d3e723600e612ee","datavalue":{"value":"7434420","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2052722$75104334-D77D-42DF-B99B-3F50C2267517","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c8c54d601f41c5cf2b19e8d5147eddeea698eca","datavalue":{"value":"Reeb graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2052722$880678C9-A715-4608-9140-D59E412C0355","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34b44e7b40021effdee26093512bde7058814281","datavalue":{"value":"stability","type":"string"},"datatype":"string"},"type":"statement","id":"Q2052722$AECF93CD-C7AB-4943-A544-78AD76534135","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"af5fa50f6b601e5db95d16957ba363ebf9e1b5d8","datavalue":{"value":"quotient metric","type":"string"},"datatype":"string"},"type":"statement","id":"Q2052722$00021E8E-B6A2-46C0-8F4A-F269F5F542D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91c92c699214b9d1be7a56f31bd929aa164bb428","datavalue":{"value":"edit distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q2052722$AB036F1D-2000-46B4-B995-6DA8A86403E5","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":"Q2052722$B4AF7937-12E6-43EF-929E-682CFE2588F8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"13f81b11873037cba1f0121bec0cfb2f6ec42f8a","datavalue":{"value":"W3037363393","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2052722$5B753AC7-DB9E-44DB-B177-E575262D9CAD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"447f8d0e35bf5e216fc50c6371543ca42cf3570c","datavalue":{"value":{"entity-type":"item","numeric-id":262316,"id":"Q262316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2052722$F0780F2B-4F62-4F11-A342-8D809FFA5F79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a3e47a213f740313abaaac0f240e56851ac6d01","datavalue":{"value":{"entity-type":"item","numeric-id":4635572,"id":"Q4635572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2052722$D8995BF9-D76E-42A1-8344-F25A7FEEF4D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"969ed87dc1a1be69e78b26ac177bf65a1a9447d2","datavalue":{"value":{"entity-type":"item","numeric-id":5368706,"id":"Q5368706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2052722$4CED6634-1CFA-481C-BC11-207253BA8757","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"049c96be307071801f4532fd2a9a2573741a1111","datavalue":{"value":{"entity-type":"item","numeric-id":658416,"id":"Q658416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2052722$970B8B85-5A3B-470E-9285-EED471F61966","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a754bfbf1eeac60886ee48f2300ed76add8895a","datavalue":{"value":{"entity-type":"item","numeric-id":2343367,"id":"Q2343367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2052722$A76E7BCA-F820-4D50-87B3-DA4B9E48AA02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0342d1401f57710dff42b65e52c6c27f7de3977c","datavalue":{"value":{"entity-type":"item","numeric-id":866974,"id":"Q866974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2052722$F6D1CFB1-0545-4192-BAAD-27DE7F15F8D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a48d3a0228cd047c8e6d03ecd0a93eacd6908b21","datavalue":{"value":{"entity-type":"item","numeric-id":966491,"id":"Q966491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2052722$E8CEFF05-1A4C-442D-9562-8FBB4E243670","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a35f5e7370239c9a93686dc715ce6c142dc7201","datavalue":{"value":{"entity-type":"item","numeric-id":309649,"id":"Q309649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2052722$A91DE2AF-93BC-4C23-9E37-22F61FA6352B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62f0299c7ed89cf820574b9d48cf29878a945e2d","datavalue":{"value":{"entity-type":"item","numeric-id":4656457,"id":"Q4656457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2052722$A66DD7DA-CBD7-4A89-B442-59C02A4851BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d8a86db0c5e2e1a4c00ae26c8c6a78414923ae5","datavalue":{"value":{"entity-type":"item","numeric-id":2912310,"id":"Q2912310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2052722$BECDF47F-EF28-451A-BAA9-05795C1D4D56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae35b42269b65df7a1c59338bf97c0ea301c5c81","datavalue":{"value":{"entity-type":"item","numeric-id":2488567,"id":"Q2488567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2052722$B1545C1A-DFCC-4650-BAD8-A1E352CC9CB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6033f4c2096ad717675a9c5eb1b469720b411a4","datavalue":{"value":{"entity-type":"item","numeric-id":2355328,"id":"Q2355328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2052722$70B0D4E3-12B6-4B97-93A7-67583FB75D72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd4615e3948dd76ee93d7fcb94c46e63c78b3bf2","datavalue":{"value":{"entity-type":"item","numeric-id":4609919,"id":"Q4609919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2052722$093E2BA1-C525-4A75-91B3-B0737D03C479","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c83a7758ec4ea2124deacc6b229d56a339a88dd2","datavalue":{"value":{"entity-type":"item","numeric-id":5845505,"id":"Q5845505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2052722$2C6D6436-E038-41EC-B37D-3755C3D34D05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27b8bc3bb963c867bf3e2413bb2278de46f1a7fa","datavalue":{"value":{"entity-type":"item","numeric-id":5139290,"id":"Q5139290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2052722$40E1EA5F-2565-4107-B75E-3D37310CC23E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80d30ed2e46f4826f27b6f8ead4d7c8f1289fb13","datavalue":{"value":{"entity-type":"item","numeric-id":4273703,"id":"Q4273703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2052722$8676CFC5-9A46-440A-A007-84AA113148E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f01c9accabc6c17f8442594153e7485fd042c066","datavalue":{"value":{"entity-type":"item","numeric-id":5075834,"id":"Q5075834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2052722$C64B4165-B872-4929-970A-B1831185CFA6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"95a1feaca6aab152d65652a784a9033b938723d2","datavalue":{"value":"10.1007/S10208-020-09488-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2052722$B62C0B78-EE1B-4D0A-9A1D-E10E64F038BD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16f025d619e7c564fb924daf0a8521ced7514955","datavalue":{"value":{"entity-type":"item","numeric-id":262316,"id":"Q262316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"efd3b439a1994a3329009b0035b6a0669aa19ae4","datavalue":{"value":{"amount":"+0.8603611588478088","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":"Q2052722$99ADC8E9-35F9-4CDA-BB3F-30F061381390","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f94c826999bfd0be813bd60872f8060bb5fb0479","datavalue":{"value":{"entity-type":"item","numeric-id":4635572,"id":"Q4635572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fc4681a47e8caca8bb27d470a1b1749cc90a075","datavalue":{"value":{"amount":"+0.8559999465942383","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":"Q2052722$AC765C06-2E46-4B7F-AC5A-0392B3E35726","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b56b7dc11e0cbb4d988786cb36fb0fa79ae8bc47","datavalue":{"value":{"entity-type":"item","numeric-id":3190079,"id":"Q3190079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ff803d7ac049e93f27bebe60f0f1cc372defd45","datavalue":{"value":{"amount":"+0.8490952849388123","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":"Q2052722$9EE1D4A4-57D5-43A1-8E30-A329C1997947","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd41535de93e1c806b555c99d45d295a36d42777","datavalue":{"value":{"entity-type":"item","numeric-id":2912310,"id":"Q2912310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de24c19c94ab81675fe11be2333047c85106a409","datavalue":{"value":{"amount":"+0.8361701369285583","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":"Q2052722$01B42784-32BA-4F2E-88BE-9E02BEB45EF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4aa99a0028180aadee91b66f0953cf9fd0e78b4f","datavalue":{"value":{"entity-type":"item","numeric-id":309649,"id":"Q309649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf0c72a6d14c3c88440f70cc2c7185c913c62472","datavalue":{"value":{"amount":"+0.8212592601776123","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":"Q2052722$FD271B28-5426-402B-9B30-6A0E69CE7C6E","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2052722$FBCECB05-936A-40B7-B018-8BA6EA84338E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2052722","badges":[]}}}}}