{"entities":{"Q1382254":{"pageid":1392994,"ns":120,"title":"Item:Q1382254","lastrevid":67304508,"modified":"2026-04-12T16:43:33Z","type":"item","id":"Q1382254","labels":{"en":{"language":"en","value":"A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1133152"}},"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":"Q1382254$0B6162A8-95AE-4727-B96B-A5C796C20355","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"938551c60030b7bfaf7f9194aaf5c333b3964343","datavalue":{"value":{"text":"A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1382254$29D1725E-7A53-404D-BC0D-646AE8A1C37A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"37b44ba538ddd46dbb9c8334c90c281efd52ff28","datavalue":{"value":"0912.68153","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382254$A1FAA5B7-1BDC-4FF0-AE2E-5525066B5415","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"da80cb60fe47a5296ae93433f6641ea9af0d20ed","datavalue":{"value":"10.1016/S0166-218X(97)00076-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382254$ECB89854-8E00-4BFE-95CF-41C60A61DB79","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e7a60909d1c148a53c40db1baa3543530a5558fa","datavalue":{"value":{"entity-type":"item","numeric-id":176697,"id":"Q176697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382254$1F050945-74FA-4B4D-9EC6-2ED833F6CDB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"73fb56bb2c6799cbe2d549466466c1fb6f1233b8","datavalue":{"value":{"entity-type":"item","numeric-id":918990,"id":"Q918990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382254$31C9F5AB-0B8F-4C15-AD37-2F5BD7807DBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e5e246b2156a66b2ef031cfcf9e9cd6a9e9aa0f2","datavalue":{"value":{"entity-type":"item","numeric-id":431807,"id":"Q431807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382254$CB8ADCB9-541F-405A-AFCF-B9F366352233","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382254$8897F9FC-90A9-47AA-81FD-0E6531D739A8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6a269028de92bfdb90854f91fbddbc8c7e99c0ca","datavalue":{"value":{"time":"+1999-05-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1382254$9310EB99-320F-4C0E-9CF2-C18ABF7D29BD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"21b77d7c30c01bda71a2076d0490b1cff484ee64","datavalue":{"value":"It is well known that every \\(n\\)-vertex planar graph of maximum degree at most 4 has a drawing in the plane such that its vertices are points of the integer grid and its edges are nonintersecting paths in the grid graphs. Moreover, each edge may be required to have at most four bends. In this paper, a linear time algorithm is presented which produces such a drawing with at most two bends per edge (with the only exception among connected graphs being the octahedron for which three bends are necessary), and so that the number of bends is at most \\(7n/3\\). Moreover, the drawing can be enclosed in a rectangle with area \\((n+1)^2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382254$92352FC8-2B86-4500-B3F3-B6B415B84CA3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382254$0E225EC4-0709-4855-9CE1-1753F6A0B7F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382254$540B3E03-5B9A-40A1-82DA-BAFE73158F26","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d7ef8f5707ce02f13d36fd3533c60a1a48ab14ce","datavalue":{"value":"1133152","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382254$65FFC56C-90FF-499F-95B9-0D7622ACC69C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382254$0B8203D1-A8BF-4966-A002-4182131B2044","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8387b89b44d46f1e44515f59158f118014e32743","datavalue":{"value":"drawing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382254$6DD3FB4D-A2D5-4243-A9BA-3F0F87B524E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c3d009c78b4a6a98a7e969740d48b52bd7730b8d","datavalue":{"value":"grid graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382254$D368E58C-2EAD-4C86-9130-0DD2AAC50B5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4c27a8414208eba22b391b2c3a982e6e5e1d84b","datavalue":{"value":"linear time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382254$20DB6366-53C0-4D31-88FF-6055A790EB8E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"abf255b967b94e917e05e1834cde56652b9b0e09","datavalue":{"value":{"entity-type":"item","numeric-id":181823,"id":"Q181823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382254$F9F9D645-0E50-4893-B894-4FE9F21B3C7A","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":"Q1382254$866E4DE1-C3B0-4DEB-8921-F840C25EE76D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec747139a1c0337971d4c72f5b8e22c5319d1889","datavalue":{"value":{"entity-type":"item","numeric-id":916362,"id":"Q916362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382254$DC275F88-9573-468A-BFF4-6174B93BCD00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d23798dead80896b65de40a7df4bba3b271179d","datavalue":{"value":{"entity-type":"item","numeric-id":1107990,"id":"Q1107990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382254$F0D216C0-19EE-421B-9693-798103E3B678","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8415b009284303875a66181cc4f8d4c22def4b1d","datavalue":{"value":{"entity-type":"item","numeric-id":1210706,"id":"Q1210706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382254$6D210F26-63C0-40B9-8321-3C5F9CD1E068","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a51cefae521f6dd1f32b795aa0f8aafdbbba7fbc","datavalue":{"value":{"entity-type":"item","numeric-id":1167194,"id":"Q1167194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382254$9B66FB94-5505-4A08-9222-012673B0149F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cb6d330b0ba17ea9706ff485bd2cc7e5caf6771","datavalue":{"value":{"entity-type":"item","numeric-id":3883524,"id":"Q3883524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382254$76FF6527-1EFF-40A1-AF87-DDD196A9C195","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e9482ac52774f29c3e0eabec830d52edd86da50","datavalue":{"value":{"entity-type":"item","numeric-id":1231771,"id":"Q1231771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382254$8D6D6A5D-62A6-4EAE-913B-B908FA4DCBC6","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":"Q1382254$309BD1C3-4F5A-4F48-8E73-B03E4E73F89C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a82d28a36950069f2ffb96a8a86b50be4149ba81","datavalue":{"value":{"entity-type":"item","numeric-id":4206752,"id":"Q4206752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382254$FEB500EA-55EA-4092-A21E-A7F8408EF521","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7871dc2cc85bb5a8983590b741f23a06f01bacee","datavalue":{"value":{"entity-type":"item","numeric-id":5596083,"id":"Q5596083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382254$DF383666-6133-4698-B50D-BCFA746F02FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"470f8820c331f2b104618004e64d62b7130a9891","datavalue":{"value":{"entity-type":"item","numeric-id":1117237,"id":"Q1117237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382254$6ED650FA-0AA6-46E9-8A75-E677BB59EFBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3aca63fd56d1f5668aee45849b4ae8e5578e768b","datavalue":{"value":{"entity-type":"item","numeric-id":809088,"id":"Q809088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382254$56C23CC5-DFD3-4D05-8E78-4EE88DBA7F46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7aefbe29064a8f1dab0c10a1ce35cbf41422e965","datavalue":{"value":{"entity-type":"item","numeric-id":4716822,"id":"Q4716822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382254$45D3C4FE-B039-4C87-9CDA-5047CB865B27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46922753362575a6fb809bcfc673ff1c32b6470e","datavalue":{"value":{"entity-type":"item","numeric-id":5528475,"id":"Q5528475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382254$E8823636-F47F-4E5A-A5D4-55C3A3160E5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9d55200a76851cc4f5881a1a995e69ae1286c7c","datavalue":{"value":{"entity-type":"item","numeric-id":4140364,"id":"Q4140364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382254$50D9E04E-A3B9-466D-92B9-10DC3E91C7B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65e4ac8383a5dc00558d164b58ab395f6f25babf","datavalue":{"value":{"entity-type":"item","numeric-id":3338119,"id":"Q3338119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382254$BDD36EA9-1D44-4216-AAB5-D116868BC34E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bcbbff114a69b8496ecebe56d464c530b778e1c","datavalue":{"value":{"entity-type":"item","numeric-id":1057281,"id":"Q1057281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382254$357A5941-CAC3-456D-964A-119E8ED97430","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":"Q1382254$BF522893-64B2-4F7F-9F29-7352E99A2C0C","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":"Q1382254$3C7DBC34-7FBA-4CEB-AD83-E73E00548262","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a791e6b13200f21127f48f475b5988c15175f95b","datavalue":{"value":{"entity-type":"item","numeric-id":5663889,"id":"Q5663889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382254$9D8876AE-D57F-4470-9D7F-2B8C98514089","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":"Q1382254$DDDCAEB4-F326-424C-9FD1-0943DCECCC5D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f77622e32787392994eed8a5f83776694af5c400","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(97)00076-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1382254$B750AEBF-6E28-4607-952A-655C3329E1CF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ac2c4b927690aebba8bbedef47bf8bc44d715a7a","datavalue":{"value":"W2012855423","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382254$87A2B8FE-4090-4DB1-98C7-47D78C0A1EB4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23f46794027b3a6695bf09fcfc71b9b288e60011","datavalue":{"value":{"entity-type":"item","numeric-id":2741461,"id":"Q2741461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"515300054c2a249fc49746bfb07325b9ef9566b5","datavalue":{"value":{"amount":"+0.8644113540649414","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":"Q1382254$4EF33E72-49B0-4B63-B51A-1EB7EA3FC473","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43997f50391e5faf54b49c50e77eeb2eebee2f45","datavalue":{"value":{"entity-type":"item","numeric-id":1902892,"id":"Q1902892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d25ddc72b1f16121e4765c7fea8c3f03c7a90c89","datavalue":{"value":{"amount":"+0.8629507422447205","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":"Q1382254$2DC1627E-27AC-4359-B29B-43C90F933F4B","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":"b893b45404e818dc6b861d32bb84fb1a35afb281","datavalue":{"value":{"amount":"+0.8513616323471069","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":"Q1382254$F263840E-97E9-421A-812A-E35C22896779","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":"2642e4d942e1f1e743be5b0bbfcc35e0fb91389e","datavalue":{"value":{"amount":"+0.8499717712402344","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":"Q1382254$9F62C2C9-F9FE-4AA9-AE8B-74064EB03640","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77e70b468fe2d1a0c72f2b56e5eb96c9659b1207","datavalue":{"value":{"entity-type":"item","numeric-id":1827866,"id":"Q1827866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8be06cb1aad5268b8a477988e3c526d18b322724","datavalue":{"value":{"amount":"+0.8460110425949097","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":"Q1382254$A6BFB11E-9BA6-4DE9-A944-44651F5D2A0E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_linear_algorithm_for_2-bend_embeddings_of_planar_graphs_in_the_two-dimensional_grid"}}}}}