{"entities":{"Q804582":{"pageid":806430,"ns":120,"title":"Item:Q804582","lastrevid":49504201,"modified":"2026-01-07T09:05:45Z","type":"item","id":"Q804582","labels":{"en":{"language":"en","value":"How to draw a planar graph on a grid"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4202273"}},"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":"Q804582$1024B20B-712C-48A6-A325-6A77EF0EA344","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2771eef85f3cbb327307c132eb376ad01141d310","datavalue":{"value":{"text":"How to draw a planar graph on a grid","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q804582$690C9DB7-6F82-4BE3-A117-2428103C1491","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9dafcef35773f3051b901e18e764471fdb94bc50","datavalue":{"value":"0728.05016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804582$A89BE4E5-A0FB-4C1C-9FAC-5B1B76EC096A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"aece03c2b664399738070b147bf69ea60c5eccae","datavalue":{"value":"10.1007/BF02122694","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804582$66B916E6-1FEE-4451-B3A6-ACFF96C47327","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"548881cca2bf6255575479a75e687a7b3fb7e7a2","datavalue":{"value":{"entity-type":"item","numeric-id":175579,"id":"Q175579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804582$55144FBD-DCC4-424F-9F1F-EC63AD1ED695","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b81a4dc49f2cef20908ab5b4ec5273f96d074360","datavalue":{"value":{"entity-type":"item","numeric-id":188717,"id":"Q188717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804582$7B8ED5C7-C138-427A-ADCF-33CCCF2539D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e454670a723c77bf11fbfb3fd80a9a00df4238be","datavalue":{"value":{"entity-type":"item","numeric-id":238454,"id":"Q238454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804582$23D8ACA2-A58A-4BDB-827B-0BCDC01C9764","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804582$BACE4585-0F61-4837-B101-8F2B4E9E5105","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q804582$EF0D25E1-E4E3-4298-90AA-5EDDBAEEBAF8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7564d60bd57ee92f9b5c4a2524c3348c0c1490a8","datavalue":{"value":"The authors show that every plane graph with n vertices has a straight- line embedding on the 2n-4 by n-2 grid, and provide an O(n) space, O(n.log n) time algorithm for finding the embedding. On the other hand, they prove that any set F, which can support a straight-line embedding of every planar graph of size n, has cardinality at least \\(n+(1- o(1))\\sqrt{n}\\). This settles a problem of B. Mohar.","type":"string"},"datatype":"string"},"type":"statement","id":"Q804582$6E377612-8371-4461-9FA5-A186370AD8BB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"90c78b3265eaf03d2c9093f31b0f9730424156f8","datavalue":{"value":{"entity-type":"item","numeric-id":175610,"id":"Q175610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804582$16BA1952-CB54-4B62-8DA6-D772F2F00CB6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804582$6D7B7110-EFDC-4901-BF30-AF74C31843E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804582$BE56B5B1-C10C-4A06-A4B2-54EDDD201E55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804582$58946EB4-32C5-4DF9-8E6E-8DF9899E90EA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"35c2e6a78b3ef1c84fb4e4b72bb5cc54fcef4ec7","datavalue":{"value":"4202273","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804582$3D3A9F54-BE6B-4833-B636-33B4FA531CD1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"725240c0ffca1653f98d62d4dc1bc36d34835bf4","datavalue":{"value":"planar grid","type":"string"},"datatype":"string"},"type":"statement","id":"Q804582$FAFFE8B6-BD2D-4511-B1E0-6F5C603E1FBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q804582$444DBBE8-0D3B-45CE-8146-797EB7C6DBA8","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"39111a7a87a2dc5bd5983848f7840505891eef12","datavalue":{"value":"Q57253826","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804582$22DE2CE6-BEED-4604-89B0-6585C527534C","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":"Q804582$CD7FAC97-390A-4769-88BA-3718B83CB62C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"21fdabb00dd7adabc0c0251c6f1d03d83bd8ebe1","datavalue":{"value":{"entity-type":"item","numeric-id":1052327,"id":"Q1052327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804582$E02043E5-DC1E-4ABC-B125-FD49F795A3EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2efb7b91a99bf82ca0c5183eabf701dd08b3c67","datavalue":{"value":{"entity-type":"item","numeric-id":5786239,"id":"Q5786239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804582$C3678751-2085-45B4-A721-ED050CC28548","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba838fdee5bc63055b0afae3a6a1506c97a6e142","datavalue":{"value":{"entity-type":"item","numeric-id":4065028,"id":"Q4065028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804582$9F3778DA-0989-4DE7-9916-0F5CBDC4B7BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af2dc51f455e8035861032dfb9491c0817f3e724","datavalue":{"value":{"entity-type":"item","numeric-id":1085168,"id":"Q1085168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804582$01B9CF45-4332-48A7-8CED-208B1363286A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36313581e6a77d3533a1cd4630fd340bdc11d5ec","datavalue":{"value":{"entity-type":"item","numeric-id":1121926,"id":"Q1121926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804582$83270B6D-53D3-459C-B221-B64A22F0D6FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d559325bc6d150c41f7e7c490b2a619364a89614","datavalue":{"value":{"entity-type":"item","numeric-id":1085167,"id":"Q1085167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804582$FAF6AEAC-7C79-4EA2-90A3-01944D75DE98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d990a995876f36f7ec1a091c259d6d4e2b928d58","datavalue":{"value":{"entity-type":"item","numeric-id":5724435,"id":"Q5724435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804582$32B7BC59-6A4A-4BC4-932C-87A42137CF43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28d1d1cb66d27d2e53aba37392ad47b61e11f859","datavalue":{"value":{"entity-type":"item","numeric-id":3326832,"id":"Q3326832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804582$B131793B-3E0E-4853-88EA-7C49FC86E396","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcc67d47bf3c27fbeab166391b3b3e9d154ed32f","datavalue":{"value":{"entity-type":"item","numeric-id":3904539,"id":"Q3904539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804582$E50C808A-89C7-41EC-8F7D-9063D6A055C9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7d03afb74362e557efbab2e0012d12fc07e79c7b","datavalue":{"value":"https://doi.org/10.1007/bf02122694","type":"string"},"datatype":"url"},"type":"statement","id":"Q804582$DF15002D-E9D6-48F9-9B81-B6B44B4D98D3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"abe6058c35bfd7277e458a906cc9904ad30ffdf3","datavalue":{"value":"W2003525146","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804582$4A641EFE-3FC7-4602-A67C-7A3280590429","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"5f0b60a7de8531ed4272b32d432123678786b335","datavalue":{"value":"journals/combinatorica/FraysseixPP90","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804582$E390DEF2-EFB9-47B9-B4F4-CDE3DD5E7714","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0b0919d5f8d693458ef2cc590a1cee29cd82caf","datavalue":{"value":{"entity-type":"item","numeric-id":3138887,"id":"Q3138887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b4a5b8914148cea7e748c42517653724133d92d","datavalue":{"value":{"amount":"+0.9431031942367554","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":"Q804582$780DDF45-C3C5-41D2-B911-60A03619C9A8","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":"7f230e4236e6413f248897a116f9d639115f55d6","datavalue":{"value":{"amount":"+0.904408633708954","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":"Q804582$EF363D02-BA82-438F-BAA4-A8D3AAC98AFA","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":"847ad080b3f59d50bcf0a715409fb45c685905e8","datavalue":{"value":{"amount":"+0.8987336754798889","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":"Q804582$CB97E10F-E56C-47D9-A575-7352C213A4B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f1763cdf18d83265b6f839559b3380293eeb645","datavalue":{"value":{"entity-type":"item","numeric-id":4431088,"id":"Q4431088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d4add2b2b4a96042bb420b07b34af41873e27d9","datavalue":{"value":{"amount":"+0.8863478899002075","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":"Q804582$3207DC28-2FD0-4BCB-922D-CA8F97FA1A1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33bd0bd5ee563a82db04dbf5177ed6f467e5c42d","datavalue":{"value":{"entity-type":"item","numeric-id":1355197,"id":"Q1355197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3529f865b3e6010a3ce45d54b58585b84aea4f64","datavalue":{"value":{"amount":"+0.8572214841842651","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":"Q804582$2E66487B-3BC7-41A1-86F7-53AE0FACABC2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:804582","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:804582"}}}}}