{"entities":{"Q1111399":{"pageid":1122148,"ns":120,"title":"Item:Q1111399","lastrevid":80261195,"modified":"2026-05-06T15:47:29Z","type":"item","id":"Q1111399","labels":{"en":{"language":"en","value":"Embedding rectilinear graphs in linear time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4076654"}},"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":"Q1111399$675883D6-377C-4C15-8A2F-A12664DC395A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d2627be0442862edfdd7c298e2afab7ff9d37ec4","datavalue":{"value":{"text":"Embedding rectilinear graphs in linear time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1111399$764494E3-283D-417A-AAD0-4C2EB0C8BC55","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9ea8cdf4feead0c0a1c210371eb9dfbce16900be","datavalue":{"value":"0658.68086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111399$D32D3D93-64C3-46CC-8A15-8EFE2E64E993","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"454706738332e0cd0206da317ffa628b5657354d","datavalue":{"value":"10.1016/0020-0190(88)90032-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111399$FDF1707B-D37F-48EA-B054-F66F3602518B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"112db2403d4bb6dac57c649d823ea78d044ea189","datavalue":{"value":{"entity-type":"item","numeric-id":1111398,"id":"Q1111398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111399$AC95C48E-7586-4004-97F9-71CBCD9BBDEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d634f408e7931005285322c857f899d254e61bc4","datavalue":{"value":{"entity-type":"item","numeric-id":580366,"id":"Q580366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111399$5C369E14-0D53-402A-B58F-802C1CA1045F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111399$B9EAE366-9E19-45C1-8259-15CC6952206C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1111399$EADFEE8C-07E7-4623-A650-DD390008D2D7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"57107c987d231ed3da9ce5028a3665ca81815905","datavalue":{"value":"A linear-time algorithm is presented to recognize and embed rectilinear graphs which are embeddable on the plane. Previously, only the \\(O(n^ 2)\\) time algorithm of \\textit{G. Vijayan} and \\textit{A. Wigderson} [SIAM J. Comput. 14, 355-372 (1985; Zbl 0568.05024)] was known. The algorithm described here uses a different and surprisingly simple strategy.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111399$A94C5A29-15DD-4520-94FB-71E068B99139","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111399$941F2839-D7D3-4814-8B7E-2038137A8205","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111399$0244431E-8A50-4240-BBB3-3DBD2E184756","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7ede79025527863c60da619e6b7d2d2cdc34ed77","datavalue":{"value":"4076654","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111399$C2B25253-2FE5-4CE7-9052-348063A64B27","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ba9992e11c5a892ccd97460fbc31ceefeeb8b95d","datavalue":{"value":"graph embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111399$669BC11C-60DC-419E-8E8D-400821D16EF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5186fd99999e6921db65766363ee98e6a615dadc","datavalue":{"value":"linear-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111399$08C78DF9-632D-48F9-8F24-06D57F487E52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"97f35ffa6c221e2f9387afb60acdfb59746850dc","datavalue":{"value":"rectilinear graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111399$51F10C6B-9794-48DD-9856-36AD349F92CA","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":"Q1111399$A3DDF572-B0B7-48A4-81C2-0CB0BF12DE46","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"18c0cbe15743905d22989300f443ef14796cf796","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90032-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1111399$194BC4F5-EC6F-44D1-A68F-51D38E6E4ED7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"eae667f6dec4f99174cd5b5e43f7822991f6e13e","datavalue":{"value":"W2166449951","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111399$1D5E87AD-4246-42F7-B5B4-BB5E8AB414CD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f41a901fdc1312944c24bc26748a05b7e032e5b","datavalue":{"value":{"entity-type":"item","numeric-id":4191609,"id":"Q4191609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111399$F813AF0E-DDE9-4574-B7D2-5B296835F9DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"622699e24c990cf5e16598fcf6f919585a0e5792","datavalue":{"value":{"entity-type":"item","numeric-id":3911393,"id":"Q3911393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111399$8FCB6B8F-34FF-4592-910C-20C88273587C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e5d96b7067c6c0958e0ec7ad41ebbe2b9a2cd29","datavalue":{"value":{"entity-type":"item","numeric-id":3674695,"id":"Q3674695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111399$2A668789-CA85-40FF-87C3-9AEF4321BC76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b42f7a383228ffac2c391b9f0dd27ad17bf285b6","datavalue":{"value":{"entity-type":"item","numeric-id":4192084,"id":"Q4192084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111399$76B86E9E-2FC3-4F66-91AC-8D6285AB5AEC","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":"Q1111399$2AC3DF6C-E30A-405B-B3B1-933A25ED3281","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04208cff725c511590f0d0e1b30a73cadd4b6df2","datavalue":{"value":{"entity-type":"item","numeric-id":3684138,"id":"Q3684138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111399$BCB9619F-539A-4E93-94F8-2B41DDD8FE77","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d380ebd38a45d88c503071b3e469d9ad08b77484","datavalue":{"value":{"entity-type":"item","numeric-id":3684138,"id":"Q3684138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4846916b4ca196b5a327de88f9ff70497bc52d1","datavalue":{"value":{"amount":"+0.8470003008842468","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":"Q1111399$9475FFDA-7E2E-4AB8-AEDB-95E2CCB2D3B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd196aa285e888bef335eb39239b9ac185f98ac3","datavalue":{"value":{"entity-type":"item","numeric-id":809088,"id":"Q809088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b78794a3d9ffb52178ee9e5e05631fa02e8ff55","datavalue":{"value":{"amount":"+0.8272192478179932","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":"Q1111399$088F8A89-A7A2-4748-9367-7DEA011E35E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2033e403f8dbacc718bcfa128a4cf0d6679fee9","datavalue":{"value":{"entity-type":"item","numeric-id":673676,"id":"Q673676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d6ea1593a4d5ef9431daefcb16ebb7462b750ad6","datavalue":{"value":{"amount":"+0.824537992477417","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":"Q1111399$8CA17DEC-DEE9-49BC-8B71-26ACD7B5FC00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15283d49a8f1054291da5ec0eb1c08b41070a4d2","datavalue":{"value":{"entity-type":"item","numeric-id":3183081,"id":"Q3183081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9dffcbda36465fa0115b0e1dbce176ac22cfab49","datavalue":{"value":{"amount":"+0.8245336413383484","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":"Q1111399$3F505494-FDED-4CC3-AFA1-741E83F0AFF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a78786faf32cf37dfd18bcac9dffe90384a917c","datavalue":{"value":{"entity-type":"item","numeric-id":2123284,"id":"Q2123284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd3dd465f8583de4da4390057033f0872da409f5","datavalue":{"value":{"amount":"+0.8171077370643616","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":"Q1111399$30457586-697C-42B8-8A1A-06D069E751A7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Embedding rectilinear graphs in linear time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Embedding_rectilinear_graphs_in_linear_time"}}}}}