{"entities":{"Q1335404":{"pageid":1346143,"ns":120,"title":"Item:Q1335404","lastrevid":67434576,"modified":"2026-04-12T17:44:23Z","type":"item","id":"Q1335404","labels":{"en":{"language":"en","value":"At most single-bend embeddings of cubic graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 646765"}},"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":"Q1335404$89DE5DAA-5963-424D-9FBE-55F85B2630F6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"62785ced57b1934ec27a34a1a927d7cb2d48e314","datavalue":{"value":{"text":"At most single-bend embeddings of cubic graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1335404$CD0B486B-38DC-48AB-8A65-4CFC7EFE01E8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4937a5fe794f719beb6a9e43bc50d3e90cbaa45d","datavalue":{"value":"0808.05039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1335404$0F5B8429-2003-4E8A-9C14-ACE815B9F9E4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cc7016c965dfb4078215963467d569f568679f2a","datavalue":{"value":"10.1007/BF02662066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1335404$8C81C963-01B5-43D5-91C1-D3CE755ED54E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e8478b1e82dab9f5a8b59e15bbcf31c979f7cb2c","datavalue":{"value":{"entity-type":"item","numeric-id":186582,"id":"Q186582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1335404$F7756C69-2CD1-4E1C-8532-09ED7F6C3DDB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b0cdb8d4632321c5e466c8887652aba3de4959ca","datavalue":{"value":{"time":"+1995-03-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1335404$AF025982-2A0E-4805-974B-998177ECBC57","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c14dedfef5639771bb2a849d6a1edec11167ab40","datavalue":{"value":"A graph is said to be single-bend embeddable if it has an embedding in the plane for which every edge consists of at most two horizontal or vertical line segments. (A bend is the intersection point of two line segments, one horizontal and the other vertical, whose union represents one edge.) It is shown that every cubic connected planar graph except \\(K_ 4\\) is single-bend embeddable. An \\(O(n)\\) amortized time algorithm is given for drawing a single-bend embeddable cubic graph of order \\(n\\). It is shown that the minimum total number of bends for a single-bend embeddable cubic graph of order \\(n\\) is at most \\(n/2 + 1\\); the result is best possible. This study has relevance to VLSI design.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1335404$97E37116-F138-4C00-979E-3613AA5413EE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1335404$5B77903C-AA90-4590-8488-E52B3AF8AD60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"007f7f82691f1d7656215e5be329d57b0bfdf5e7","datavalue":{"value":"94C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1335404$10B78477-A12C-4F64-9EA6-2023C53B2F14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d5ada37b1398532b96572a582dac34014ee17ec","datavalue":{"value":"57M15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1335404$AB3F6CEF-B666-459D-80B1-B585E8BC298C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"485a8ba99b2f47e28f08bf4a86659fb6669b92e6","datavalue":{"value":"646765","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1335404$2B680FE9-06B2-4FD2-A697-763DED8B10A4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb701f14a88cf07fc0e557f0c714ad663b5c7358","datavalue":{"value":"single-bend embeddings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1335404$0D3E228E-3DDD-4D51-BE01-D85CBB7606A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"93cbb2598457bc7d69b5a536074cc48914824680","datavalue":{"value":"plane","type":"string"},"datatype":"string"},"type":"statement","id":"Q1335404$A16F1789-295A-400C-8DEB-BC62D192596E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"758716f742b3fda9b4acfca54a882c1227ddce3a","datavalue":{"value":"bend","type":"string"},"datatype":"string"},"type":"statement","id":"Q1335404$23EA9449-EC4F-42B6-9C1E-F97B9E55F80F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e01f33e43354d516b8d6e654c1ded76a55047726","datavalue":{"value":"cubic graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1335404$317154CF-1E02-45B6-8C5F-9D02955AE7CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"38dd5c31d373d76e6308be0f17a0875fd182b166","datavalue":{"value":"VLSI design","type":"string"},"datatype":"string"},"type":"statement","id":"Q1335404$9645258F-0C80-448B-9F49-B96F9AF74A03","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":"Q1335404$0F2E6659-5CCB-4A93-AD7B-13B52B5D0245","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d05e725fb49325525389da6ba06c5ff495418d98","datavalue":{"value":{"entity-type":"item","numeric-id":1210237,"id":"Q1210237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1335404$95945F93-E5A6-482E-AC57-B55A8DEFCD74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2cc059d624e08de4d2dbe18a862042f4ee3ef5e7","datavalue":{"value":{"entity-type":"item","numeric-id":259076,"id":"Q259076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1335404$6D0EEA7A-C208-4FC4-9866-BA38541276E8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"205b6d05d63e09819854956633396177079e7ebb","datavalue":{"value":{"entity-type":"item","numeric-id":591987,"id":"Q591987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1335404$C47D1F68-EF82-47C9-9125-64584DCFAD8C","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":"Q1335404$73DC0351-E847-41AB-8A92-935E1F35C230","rank":"normal"}],"P223":[{"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":"Q1335404$7162DE1F-E4B3-42C1-B8DE-87850BC5759C","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":"Q1335404$7377D3A5-C3EE-410D-A65E-476AFB289455","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":"Q1335404$0631B9C7-10B3-4AE2-B7BB-EA733F99875F","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":"Q1335404$905A5D89-EB3C-451B-85C5-4128A8E9EFBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51065d25762d613ccebe13c9e5c847ea734511d6","datavalue":{"value":{"entity-type":"item","numeric-id":1210238,"id":"Q1210238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1335404$D18DA90E-26AB-444A-B72B-C118E619B05F","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":"Q1335404$2AB6393D-5EDE-4F69-A542-A37DF69288F0","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":"Q1335404$EE47C912-18CD-4D28-82CC-A1DCAABFEBA0","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":"Q1335404$6216220E-F1BC-4533-878E-955576A54FA1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"87e1143a7d93dbde152622952f7fede8427a1592","datavalue":{"value":"https://doi.org/10.1007/bf02662066","type":"string"},"datatype":"url"},"type":"statement","id":"Q1335404$7D6A1A89-01EE-49EB-914D-FEDF039CFFC9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"024e9b0a17c9814622b7ac35bffdb82221e86cae","datavalue":{"value":"W2054234829","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1335404$7B11D986-90E1-416C-9D44-14C1245EB280","rank":"normal"}],"P1643":[{"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":"7007e24f603eb54f24d4d07aa5cf137c65802347","datavalue":{"value":{"amount":"+0.8198097944259644","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":"Q1335404$D62D9988-C291-479C-93AA-1A21C6515F9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e7a21924f4662d8797aba2807d77d638e0cc112","datavalue":{"value":{"entity-type":"item","numeric-id":1210238,"id":"Q1210238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2672fa586a972e503e79ce0774e4f7465d8f48d","datavalue":{"value":{"amount":"+0.817295491695404","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":"Q1335404$0C187BC3-F41D-436F-A629-404B8AF3668A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee6779d69fd313c36649d482f67bb6c404119eb8","datavalue":{"value":{"entity-type":"item","numeric-id":3801098,"id":"Q3801098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb51728e6fd4b0f7bf0717cce8707043c32f2793","datavalue":{"value":{"amount":"+0.8082103133201599","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":"Q1335404$5F2C0D68-06A8-4DFB-8A79-1F8903B14FB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"87c1e98c9011507e705e4718cbed681bc29541c7","datavalue":{"value":{"entity-type":"item","numeric-id":4472319,"id":"Q4472319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48b652940f1358a19d9b015cf4ab8a0cadeaeb9b","datavalue":{"value":{"amount":"+0.8011289834976196","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":"Q1335404$66B7918D-00E6-4D21-A1F5-46298EACD06C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"At most single-bend embeddings of cubic graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/At_most_single-bend_embeddings_of_cubic_graphs"}}}}}