{"entities":{"Q1962071":{"pageid":1972813,"ns":120,"title":"Item:Q1962071","lastrevid":47437372,"modified":"2026-01-01T18:17:04Z","type":"item","id":"Q1962071","labels":{"en":{"language":"en","value":"Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1395035"}},"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":"Q1962071$C234BA96-11D1-40EB-A68C-78DF3EBAC314","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"64008b8ce2270296f0a467bd74c92170309b604c","datavalue":{"value":{"text":"Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1962071$9CDD860C-9375-4D08-9975-7A3C3129B671","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ab170545467a90a15131ba9d159fca3c11bbacc0","datavalue":{"value":"0949.05016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962071$66BF2E0B-A075-4C57-B9F8-C576046D0EB0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"30bc29c279a1f0a755bd005c4b5a3d5630691ef1","datavalue":{"value":"10.1016/S0166-218X(99)00161-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962071$429817D2-2FAD-4519-ACF0-A90B9858B386","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962071$5BED1A19-0819-4373-A9B0-DB8637096168","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":"Q1962071$4A9508D0-2FAC-4D7A-807D-39DF84C49B10","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"eacd2e3d947d1706227d737946fa10c2f7b5f8eb","datavalue":{"value":{"time":"+2000-11-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1962071$34508CEB-D81E-42A2-8761-99423FB3E5B3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"21b1fb6b84fc1d79cf924074056801b204372b2c","datavalue":{"value":"Let \\(T_h\\) be the complete binary tree with \\(2^{h+1}-1\\) vertices. The (extended) square grid \\(M_r\\) (\\(E_r\\)) has vertices \\((i,j)\\) for \\(0 \\leq i,j < r\\) and two different vertices \\((i,j)\\) and \\((k,l)\\) are adjacent iff \\(|i-k|+ |j-l|= 1\\) (\\(|i-k|\\leq 1\\) and \\(|j-l|\\leq 1\\) in the extended grid). All embeddings considered have total vertex-congestion \\(1\\), i.e., different vertices of the guest \\(T_h\\) are mapped to different vertices of the host (\\(M_r\\) or \\(E_r\\)) and in case a host-vertex belongs to two paths representing different edges of the guest it is an end-vertex of both paths. If we use the well-known H-tree layout to embed \\(T_{h}\\) into a square grid, the expansion \\(|V(M)|/ |V(T)|\\) tends to \\(2\\) for \\(h \\to \\infty\\). The authors give recursive constructions to embed \\(T_{2p}\\) and \\(T_{2p+1}\\) into square grids with expansions approaching \\(1.606\\) and \\(1.511\\) for \\(p \\to \\infty\\). In case of extended grids the expansions approach \\(1.234\\) and \\(1.284\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962071$7F3856B9-2CE4-476E-AA02-4F40EDE44F74","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962071$FF6DCC3C-3D09-478D-8028-1F2EC7A960B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962071$F5149BBF-23ED-43E2-B703-BB36F9C619C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962071$5675E249-120F-48B3-BD93-EC66EF053966","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962071$8E3E0AB6-9152-4FF1-AB71-9F23046517DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ca8c16691e9ec83d46a3995338b09d48ac9660ac","datavalue":{"value":"68M10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962071$65BEBFFF-71F2-49EE-86B5-1BAC24E679C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3cb322112ae56aec500b334b7351f32fb107365","datavalue":{"value":"68W35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962071$206FB8AD-E797-40B6-92A2-D7A9B28701D3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4256a889583b07c23fc198502f41b0ef4fc0943d","datavalue":{"value":"1395035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962071$76DF222C-E560-4E45-BE01-3EB3D1B5B433","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"423248905100fc54916f91dd5463beec3fe25805","datavalue":{"value":"complete binary tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962071$7D5C14E2-D7B0-4DB3-89F9-7D139C8EA932","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9c54135cce883ad7bd5025d71e73c34fb47e6792","datavalue":{"value":"extended grid","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962071$529E7768-E2BF-4E21-9E92-09873F1D320C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e7bd08d0645482afa238d75eafdc688efacb395","datavalue":{"value":"embeddings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962071$77CBB5A6-B536-4E33-A29E-D9BC473ABCF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac03ab07d4600b41cd1cb277c5f4ad6b40be3a0b","datavalue":{"value":"total vertex-congestion","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962071$BE06A1F4-5841-4F71-9C6D-EA5637B1CE4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"000dae3d5c1a4481d59258d01f80c27b7c761a85","datavalue":{"value":"square grid","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962071$B12645E4-CDA5-440B-A34A-56C22FA1B9F6","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":"Q1962071$C29B69FC-48E1-42EE-AFEB-603A7C3DB567","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bfd2907ff9a7da3813e10d03b96f39d775a43cdf","datavalue":{"value":{"entity-type":"item","numeric-id":3786430,"id":"Q3786430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962071$D738449A-4DFD-4EB8-AE9F-B2D896EDA485","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d447765b82712c353a01b176295cff842f4ea35","datavalue":{"value":{"entity-type":"item","numeric-id":4694714,"id":"Q4694714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962071$748DE6BF-EED9-4F96-BD68-D917E7A41A3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2107d78e59891d71494f59533e9f27e6532141ef","datavalue":{"value":{"entity-type":"item","numeric-id":4820160,"id":"Q4820160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962071$B475EE7C-575B-4AB2-9355-BEC90561FE9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15430f7ada58e2df90f4e0ee05ae77c7dbf60747","datavalue":{"value":{"entity-type":"item","numeric-id":3477932,"id":"Q3477932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962071$5BE3BD6A-A990-4AD7-B46B-CD5627B94D18","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":"Q1962071$7DE93047-DFC3-4B1D-A7DE-1D441E3A934F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16c62ec85eb240dcead00f2629a9383eb22c2ba4","datavalue":{"value":{"entity-type":"item","numeric-id":4028115,"id":"Q4028115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962071$14B67CE3-2FAA-470B-ADF1-A23ACF600E7F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8dbe73f57c570cbd504c42a7ff05099031febdce","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(99)00161-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1962071$E0E07210-55C2-47E8-A698-2E862659241D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b8aa300cc502d3972724404ecfde8d54d1ad1092","datavalue":{"value":"W2054681864","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962071$5340F2E8-B76F-4F5C-8624-D411561F8E95","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5572595fc1f4ad3a147835d25ad71c7376c214fb","datavalue":{"value":{"entity-type":"item","numeric-id":4938676,"id":"Q4938676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74c6fac1b00313f2496e0d7641c7dd4d6691c0dd","datavalue":{"value":{"amount":"+0.8555976152420044","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":"Q1962071$A9F7D644-F7E7-4752-9EAE-814D81B7ABEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b12ed99eaa996cf15ec1f1d7e0c09384280a96c","datavalue":{"value":{"entity-type":"item","numeric-id":2332034,"id":"Q2332034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d66c4ecde455e97c380ae5d924c03b4cfa54c712","datavalue":{"value":{"amount":"+0.8404893279075623","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":"Q1962071$C8728C97-813E-4EAF-94BF-BB9CA9A2F7A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a683d83b57817f77f1f00e85ce12021459aebb1","datavalue":{"value":{"entity-type":"item","numeric-id":4694714,"id":"Q4694714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4386825477545e25ba1d0cc7528258d264570d88","datavalue":{"value":{"amount":"+0.8391003608703613","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":"Q1962071$83132A50-EAC5-43B8-B772-7D9B2A1AEE3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96050f8f3f293f0147542b1d1012a70b5c5bb154","datavalue":{"value":{"entity-type":"item","numeric-id":5928873,"id":"Q5928873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4386825477545e25ba1d0cc7528258d264570d88","datavalue":{"value":{"amount":"+0.8391003608703613","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":"Q1962071$ED2DF261-C38F-46DC-BDA6-346E9B1BFA1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b37de27b1736bbe7ee359e229ac8be56f4c8b33","datavalue":{"value":{"entity-type":"item","numeric-id":1414240,"id":"Q1414240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7937b756d782aff5c5ea8e2f6dece5d5d0aa7836","datavalue":{"value":{"amount":"+0.837598979473114","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":"Q1962071$3A9C46E6-929B-423E-8ABF-A2320FA4D30B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1962071","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1962071"}}}}}