{"entities":{"Q1736777":{"pageid":1747518,"ns":120,"title":"Item:Q1736777","lastrevid":68870112,"modified":"2026-04-13T02:46:24Z","type":"item","id":"Q1736777","labels":{"en":{"language":"en","value":"Modifying orthogonal drawings for label placement"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042331"}},"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":"Q1736777$54AE300C-8226-4707-B7D4-1D1FFCE940F6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3d124ff7459342c0f9d1212701d3d0a7b2aaf50e","datavalue":{"value":{"text":"Modifying orthogonal drawings for label placement","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736777$87E471FE-382D-47B1-BB33-89FD3410455C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"754c593f640080a8d3531c405ea127f8a88d06ab","datavalue":{"value":"1461.68155","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736777$8E613D3D-4A74-4A4D-B456-33425DE6683B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0bd86bc7faa720aca5d69450b03bf1a1996d7a0a","datavalue":{"value":{"entity-type":"item","numeric-id":175376,"id":"Q175376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736777$0F602691-D873-46D4-8680-1A16C5F38C9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"07e8a36647ad87f394b10ef06c5d41e6f9d1c02d","datavalue":{"value":{"entity-type":"item","numeric-id":1384190,"id":"Q1384190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736777$F9CD7C04-10F6-4C5F-8C2B-C0B874D8D6D6","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":"Q1736777$D4981B33-19B8-4BFF-ABB1-4005D4D02369","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":"Q1736777$DB0DE6F4-B0F0-4013-BE07-4BAF853A9D16","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"09be4d13b4ad296ff5c0bdecb28ffaebfefd85f8","datavalue":{"value":"Summary: In this paper, we investigate how one can modify an orthogonal graph drawing to accommodate the placement of overlap-free labels with the minimum cost (\\textit{i.e.}, minimum increase of the area and preservation of the quality of the drawing). We investigate computational complexity issues of variations of that problem, and we present polynomial time algorithms that find the minimum increase of space in one direction, needed to resolve overlaps, while preserving the orthogonal representation of the orthogonal drawing when objects have a predefined partial order.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736777$C8DEECF2-9259-48C9-9669-14FB5AB6CA7A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736777$DAC1E69F-5CCF-4984-BE6E-75E9CF5976F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736777$49CEDDFF-E319-494D-86B3-DD78244B2C84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736777$A10A996D-6229-4B08-B281-E1D9FE633088","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"baab21bb388648bb5082f7e62a468784aa9b71d8","datavalue":{"value":"7042331","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736777$333541E1-564C-4C4E-90D0-DAC952370306","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b408d6d38b8b164d655579d3b757814e0594f55","datavalue":{"value":"automated label placement","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736777$ACA20421-A989-49BC-A76B-6526191B5062","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"703eacb2777b34ec9745a46d331518ca0d8878da","datavalue":{"value":"edge labeling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736777$13133E38-6E8F-484A-AC73-B92A5AF302D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a594ef9dbe8a090d158483294abcbc56f4589f9b","datavalue":{"value":"graph labeling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736777$CA6BB6EE-2D2A-4C6F-951B-888C6C876831","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4660f79db30bfe87b351634d1aa3a20de4391ddc","datavalue":{"value":"orthogonal drawings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736777$ADBAE094-F2C2-467E-B9F9-D654090E507B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e257e9a17bc983a6f139f0c77c64fcf0b8963f7","datavalue":{"value":"graph drawing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736777$3B68359B-C8FF-489E-B5C1-C4308F5186D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736777$3C9C7458-7CDD-4EE7-B4D2-6087176CDA86","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":"Q1736777$3484F0DF-E6DB-4D50-AAD5-8517BFF3C86E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"da1b29987d3e174edf57706605c3633296e3fa2b","datavalue":{"value":"https://doi.org/10.3390/a9020022","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736777$F8AC4615-06B3-47BF-9FD5-5EFE51902186","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c0729fbd14351cb8db8e15f8d434339a97c891d7","datavalue":{"value":"W2311124100","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736777$34B2F8D3-1327-463C-91D8-FD2C167A88D8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f6688a7100408f9b462c6b930a1f5145e0e4dad","datavalue":{"value":{"entity-type":"item","numeric-id":2573336,"id":"Q2573336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736777$1509AFE1-1833-405D-8562-13CA89EE2203","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa824902aabc2c8bdd82d7f1aec0a54d6f2e1e7d","datavalue":{"value":{"entity-type":"item","numeric-id":4501694,"id":"Q4501694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736777$8753E047-7805-4C41-AA17-FA9AA2512467","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"625a03d46620a33bee2de786dbc5e81f0c26accc","datavalue":{"value":{"entity-type":"item","numeric-id":3154375,"id":"Q3154375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736777$D6866E52-FDC6-4A55-9474-A17BA03C239A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b72ee5ca17c03a17dcbc27a55a074c1320958acd","datavalue":{"value":{"entity-type":"item","numeric-id":3801098,"id":"Q3801098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736777$BC544BC5-6FBE-4D4F-B266-A6F12332942E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"795d5053d33d6922d114b0161a566c61fae789ce","datavalue":{"value":{"entity-type":"item","numeric-id":1337400,"id":"Q1337400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736777$6E332007-3C4F-4C85-9446-13EB1374699B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6d04f819d33561d18482cdbafd125731d0693d2","datavalue":{"value":{"entity-type":"item","numeric-id":1384191,"id":"Q1384191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736777$9A7444B4-9A4B-498C-9153-2C50A4F851CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc69d6e2e230263bdcf681689a5cee5266cea81d","datavalue":{"value":{"entity-type":"item","numeric-id":4571489,"id":"Q4571489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736777$FB4E73E1-9458-4875-82C0-5D35E7E593AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5427a7a3f86d9eea9f0a20bc60b67a949f49790","datavalue":{"value":{"entity-type":"item","numeric-id":5931366,"id":"Q5931366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736777$101E2240-62F4-48C8-AF75-F3DC598BFB1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736777$254A9B29-C0E1-4169-9C51-6D18BC9BC373","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ea378d624c50e58a58e8431c63106791cf91efc","datavalue":{"value":{"entity-type":"item","numeric-id":4818541,"id":"Q4818541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736777$74353D99-2518-4461-83FE-FF30214C531F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e579aa4704eaeaa9ad5064e4744c9d902a73e187","datavalue":{"value":{"entity-type":"item","numeric-id":3997942,"id":"Q3997942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736777$5BB4A864-A2CA-497D-93F3-AC0FC90B2643","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"beafd09c79dfa9f43f527c7e484481f6934843d2","datavalue":{"value":{"entity-type":"item","numeric-id":3056948,"id":"Q3056948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736777$6797258A-FE35-4C57-BBB6-9A8C8286EFBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58b8f37a1e7d2ddb5b4d7a11d0fd9ef9739a4370","datavalue":{"value":{"entity-type":"item","numeric-id":5288156,"id":"Q5288156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736777$7D490272-AE39-4EEE-B1EF-D7D15EEA4248","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ba5038f145783a352a791fde450692e76de48206","datavalue":{"value":"10.3390/A9020022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736777$F02831FB-3983-4268-AAEF-C465ED4EA605","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"382da8c3dc3ff632fa779466e6c1063021b7a005","datavalue":{"value":{"entity-type":"item","numeric-id":3043712,"id":"Q3043712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d6c30b27e5bfe6fa15042d76dd4990b01238bf65","datavalue":{"value":{"amount":"+0.8439014554023743","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":"Q1736777$7ECE6D5D-A723-416C-B508-AB3E52BB3C23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8cf68c7afd5e19e7df0c5ea11228e8fe4e32bf1","datavalue":{"value":{"entity-type":"item","numeric-id":4422263,"id":"Q4422263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"586735d3b2c27d2afdd44718065b4e8f930d0445","datavalue":{"value":{"amount":"+0.8402878642082214","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":"Q1736777$2090BC1B-45A6-4731-8C3D-3C08211B2DB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b12e8a6043baa1c9246ce6bb662ea4b578fe67a9","datavalue":{"value":{"entity-type":"item","numeric-id":2573336,"id":"Q2573336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22321292e062ce0156aa6fa352d0d1615307cbaa","datavalue":{"value":{"amount":"+0.8299643397331238","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":"Q1736777$1FA65237-3331-476D-8670-764852C377D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24ed8fa7a04db6b515d499dbaa2bcd265b0bfe9b","datavalue":{"value":{"entity-type":"item","numeric-id":5301702,"id":"Q5301702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53ba77681ce0deba6b62740eeb9c4b88ae98b6d7","datavalue":{"value":{"amount":"+0.7763064503669739","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":"Q1736777$8B0B23A8-49C2-479E-9375-E66E9AA7D117","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bcb1837b36c8b875b5c71c45edc3d00d19de379e","datavalue":{"value":{"entity-type":"item","numeric-id":5945915,"id":"Q5945915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc46521f0145a810c536ad47df433dda2ef777c5","datavalue":{"value":{"amount":"+0.7737837433815002","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":"Q1736777$D8DAB31C-9D78-4BF5-A362-EDBEC270F234","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":"Q1736777$85364739-ADAA-45D6-A7B3-5D435F76DCCC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Modifying orthogonal drawings for label placement","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Modifying_orthogonal_drawings_for_label_placement"}}}}}