{"entities":{"Q1736822":{"pageid":1747563,"ns":120,"title":"Item:Q1736822","lastrevid":68870508,"modified":"2026-04-13T02:46:34Z","type":"item","id":"Q1736822","labels":{"en":{"language":"en","value":"Faster force-directed graph drawing with the well-separated pair decomposition"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042362"}},"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":"Q1736822$8AB3D662-600A-45A0-A52B-647D353D9A76","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7291f4811677586ec716db40081e0da469daac62","datavalue":{"value":{"text":"Faster force-directed graph drawing with the well-separated pair decomposition","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736822$6F7C1A57-45B9-4693-848A-959890B2A7E9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a5fbc8d873c5134118f27875aa7b99e268a113f5","datavalue":{"value":"1461.68158","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736822$CA47F669-34A3-4643-8EDA-8373D2C30FD1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ab1c612c65f14b75337d7017892145fe8ab987c3","datavalue":{"value":{"entity-type":"item","numeric-id":1725745,"id":"Q1725745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736822$1CE2EE90-1338-40BC-9374-9BDD649C09E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"83381eec9b184d4928dbc1724082cb2e43634626","datavalue":{"value":{"entity-type":"item","numeric-id":334943,"id":"Q334943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736822$34BF5E15-24AD-44B8-8610-F55895008D17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ec969d2fd43611f261aa5afd95ae2702a82857ba","datavalue":{"value":{"entity-type":"item","numeric-id":1725746,"id":"Q1725746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736822$A542B1C5-903D-43EE-AB46-16116C7691DC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736822$F23F52FC-7D88-4B99-9890-2994F3EF3EB9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-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":"Q1736822$BA5E4DE8-B183-4502-886E-C893E42D777B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7979de48e22b3d12664e613c89f561cc42ee2605","datavalue":{"value":"Summary: The force-directed paradigm is one of the few generic approaches to drawing graphs. Since force-directed algorithms can be extended easily, they are used frequently. Most of these algorithms are, however, quite slow on large graphs, as they compute a quadratic number of forces in each iteration. We give a new algorithm that takes only \\(O(m+n\\log n)\\) time per iteration when laying out a graph with \\(n\\) vertices and \\(m\\) edges. Our algorithm approximates the true forces using the so-called well-separated pair decomposition. We perform experiments on a large number of graphs and show that we can strongly reduce the runtime, even on graphs with less than a hundred vertices, without a significant influence on the quality of the drawings (in terms of the number of crossings and deviation in edge lengths).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736822$EED2423E-94D6-48A0-A0DD-3151CD8DD500","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736822$5B618B64-3E06-42F6-B6C3-1A78E9766951","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"82e8efd6e51c28a954a2ab0c3ccebf86d2ac5eb3","datavalue":{"value":"05C62","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736822$F45DAEB0-45CA-413C-ABED-820483898503","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736822$6E4B00E2-6B73-4CAA-9F61-235B535C44CC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"57b983ff363d295b43d1c916d6f2fe0c04c282cd","datavalue":{"value":"7042362","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736822$12A0A8EF-1D7A-40EE-8E54-6720D2686058","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c2e26ede2b1c42cf08f5ab3746faf1a1b8dfeb0f","datavalue":{"value":"force-directed graph drawing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736822$BEC4AD9A-ACB6-4792-B709-7EF1943DCA87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b80a30643ba74b22d22b459e4c682c5f2b89d960","datavalue":{"value":"well-separated pair decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736822$91447E69-4788-4A7F-8D81-DF8BAC1C0565","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1733aa8df411fc17c24bd2ffa287209b15e1ae7d","datavalue":{"value":"Fruchterman-Reingold algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736822$B83A81B5-5646-42EF-99B9-6A3935036F23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d0c4044b5ce8b66514340019aecd275cd3c18f6","datavalue":{"value":"experiments","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736822$E7C16CF2-FDE6-4F67-8456-363BEFDEF0D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6773a8681cb308e3c85a2fe4938dfb20fb23f96a","datavalue":{"value":"number of crossings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736822$1BFBEC91-DEEA-4B96-89B8-C1AFB8722033","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01d37cb8c616b51206fe74275f7ccf099be96520","datavalue":{"value":"deviation of edge lengths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736822$E262A6C6-78CF-42F9-9C40-24A076D81E93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5af57a20a640a228ee31952e85afe647d9beb750","datavalue":{"value":"runtime","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736822$C32A2497-33C2-4974-9313-98C827FF0850","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"f0bc0943ea959d265cae3712c1ef266fd00deb2a","datavalue":{"value":{"entity-type":"item","numeric-id":24045,"id":"Q24045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736822$D21B43E0-3F0D-4060-98D5-7A5BD38B76E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"4574d6e3d0ab332435321745ef78a645021a95b2","datavalue":{"value":{"entity-type":"item","numeric-id":16289,"id":"Q16289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736822$7BA63F80-11B6-4A22-9CBB-37244C100DB7","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":"Q1736822$ADC892E1-6EE7-4F97-BDE8-A6BDA8230A12","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0573b56197c095dc20ef71e0331ec1aa07cb259e","datavalue":{"value":"https://doi.org/10.3390/a9030053","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736822$C0A3E5C7-4DDB-4F31-AC9E-5973BD66FA07","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8a72943f9f1931fdad3c3fa4e1a59b4e90e525b9","datavalue":{"value":"W2485444378","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736822$461533B2-55CA-4F66-9BD3-F0EA0E12D1F9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ceb223009cb80134302ab696158c4e52e464a438","datavalue":{"value":{"entity-type":"item","numeric-id":4912228,"id":"Q4912228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736822$B4E92EF6-4810-459A-935E-87A724150625","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e473ce93150c7c81fc1565c1187cf5cbf52516c6","datavalue":{"value":{"entity-type":"item","numeric-id":4679069,"id":"Q4679069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736822$0E9EED8B-8840-4BA8-BC71-D0A356B861FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ee77b9d233e56b6d944b9c190b349ebff295055","datavalue":{"value":{"entity-type":"item","numeric-id":5711614,"id":"Q5711614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736822$A5D52D27-FDDE-4F31-8C1D-BD8604F2D4D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2bd07bc09dedd761e445d59a50fbc70d9fc3bbe8","datavalue":{"value":{"entity-type":"item","numeric-id":5903478,"id":"Q5903478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736822$129795C6-2958-4426-95A9-CA0D6D3C2F59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2016ef922b03861eb4810abb2fa2dfe597c9001","datavalue":{"value":{"entity-type":"item","numeric-id":3611842,"id":"Q3611842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736822$042C62D8-DA96-4137-8EF3-55F52C70965F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d50eec7b25c0c9b4bd1d88f0e7e6a7035bbb0a07","datavalue":{"value":{"entity-type":"item","numeric-id":3073662,"id":"Q3073662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736822$29CFA175-C8B2-4DC4-BA9F-29671D82E17E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"440ba0d9dbee427a1b508f6b771488e2dd84f87d","datavalue":{"value":{"entity-type":"item","numeric-id":4369857,"id":"Q4369857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736822$800495A3-EC26-4A51-845D-670F8304A695","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb9114df78baad23362e20ba049d6982001cde23","datavalue":{"value":{"entity-type":"item","numeric-id":2959742,"id":"Q2959742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736822$3ADA34B0-D348-4E6E-A23C-B9923DF40DDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be3c5a8818c4c46851df63da12a053a069982e14","datavalue":{"value":{"entity-type":"item","numeric-id":3445775,"id":"Q3445775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736822$03374A97-30A7-4906-B0D5-D7CABD9DBC08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a28190a0517e82448a8b26514eaf1c36fd326bf","datavalue":{"value":{"entity-type":"item","numeric-id":5301419,"id":"Q5301419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736822$2BC01E52-41D8-4BAC-98C2-08C6A8531A76","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9aa43954f0351c29e7c9978257c361ca5c67a3f4","datavalue":{"value":"10.3390/A9030053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736822$91658406-70B9-4980-BC16-FCB7AF3614A8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94c499d15298e0ea56042de36e4a287d66fa73f8","datavalue":{"value":{"entity-type":"item","numeric-id":2959742,"id":"Q2959742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ed0d4a8002d98ae475e924c65685a1d36c2409a","datavalue":{"value":{"amount":"+1.0000001","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":"Q1736822$9FDEE916-F716-4734-8D8D-20000A3E9211","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a6b2418baf4f7ab7bf14aa0665d298902e99563","datavalue":{"value":{"entity-type":"item","numeric-id":4472305,"id":"Q4472305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffd4c3575d6353fe2a271a1279072938587524e1","datavalue":{"value":{"amount":"+0.8978609","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":"Q1736822$134433E4-8402-4515-BB08-826039180ACA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcdf24bcff1caf5b515b7e2fdf54de19d955481a","datavalue":{"value":{"entity-type":"item","numeric-id":4679069,"id":"Q4679069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"081d53b3db6df87bd87c51aace2dbfb7c66bbd4f","datavalue":{"value":{"amount":"+0.89739496","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":"Q1736822$33C88A0A-817D-4C6D-8EBB-C0E5A3CB3410","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c846cd6abfe673078beaa47d1c63902b2d534421","datavalue":{"value":{"entity-type":"item","numeric-id":439759,"id":"Q439759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06f79e3ca5e6d14e79e0581cdcbc74b9f5fcb0a6","datavalue":{"value":{"amount":"+0.8938314","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":"Q1736822$DF6D0C25-A9B0-4BB9-839D-3B8AC8FEAF6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"788346f30b27adc6bd8d566ebcf88a0f85c99163","datavalue":{"value":{"entity-type":"item","numeric-id":1721190,"id":"Q1721190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95bc4091f9e9538806429157a70ee2b68179edef","datavalue":{"value":{"amount":"+0.8649991","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":"Q1736822$FE8338EB-5157-4F4B-9845-DAB80CC14DBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ad4f54cffa5847b91e24350a02c7258d15b0fe6","datavalue":{"value":{"entity-type":"item","numeric-id":5897634,"id":"Q5897634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"009043496c58ee5fa516b3bb93a23546b642e5ee","datavalue":{"value":{"amount":"+0.8616328","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":"Q1736822$90FBB59C-D548-45DC-95C0-5A032C61A486","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5468100141489d3889d6d5836687d2703de91dd4","datavalue":{"value":{"entity-type":"item","numeric-id":4472306,"id":"Q4472306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7c086f56e6283150a77b9899c9bfffd1d7e70c1","datavalue":{"value":{"amount":"+0.85682994","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":"Q1736822$D797EC2B-592E-4BD8-A1BF-97D21D8E767F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec88be172bba0d63b2a2c6fc2bc6ccb02e8139a2","datavalue":{"value":{"entity-type":"item","numeric-id":4405597,"id":"Q4405597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7c086f56e6283150a77b9899c9bfffd1d7e70c1","datavalue":{"value":{"amount":"+0.85682994","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":"Q1736822$40AD062B-C09C-4B02-9005-DFE18A2DAFED","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":"Q1736822$6BD97A94-FF7E-4530-9372-C6105973EA71","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Faster force-directed graph drawing with the well-separated pair decomposition","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Faster_force-directed_graph_drawing_with_the_well-separated_pair_decomposition"}}}}}