{"entities":{"Q5928873":{"pageid":8105675,"ns":120,"title":"Item:Q5928873","lastrevid":47594662,"modified":"2026-01-02T04:19:54Z","type":"item","id":"Q5928873","labels":{"en":{"language":"en","value":"Efficient embeddings of grids into grids"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1584470"}},"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":"Q5928873$403CADBF-5C40-460E-A51A-EA889928D151","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"087414b6ae96fa1631585fd8c3cebb445d552437","datavalue":{"value":{"text":"Efficient embeddings of grids into grids","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5928873$943E587C-085B-4609-8BFB-F59D05E63C40","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"de01a5828826fe2fb745e4b0335893a00241c59b","datavalue":{"value":"0972.05016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5928873$9333938A-CF53-431D-9B57-A780A9B9783E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"10c0b4478e43191f943caaacdc14d87878916ee4","datavalue":{"value":"10.1016/S0166-218X(00)00224-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5928873$3E1FA1B3-93C5-4496-9FA9-E0B9146D8549","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"91a78df43dd79bb77235709c9b9e85337d782fb1","datavalue":{"value":{"entity-type":"item","numeric-id":169300,"id":"Q169300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928873$D3B94D9D-27AE-412D-9530-B9F1435FDA36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b5738c5324cd34b03263836bb3a094081cfbb0d3","datavalue":{"value":{"entity-type":"item","numeric-id":169301,"id":"Q169301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928873$37DC95EF-B730-42B6-9A67-0A726168A11A","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":"Q5928873$C8C50EF7-C221-4F4E-8B61-DF14CCF49216","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fb718e2cdac7bb2fbda2153529198f7b2bbf7b67","datavalue":{"value":{"time":"+2001-11-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5928873$85090D9B-8621-4533-8626-DDC238997742","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f12e1eb1be75d4426df498c29926dc868c2e1814","datavalue":{"value":{"entity-type":"item","numeric-id":187114,"id":"Q187114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928873$BEF3B622-CEBC-4636-9A7B-C0FB78622CCD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5928873$446D6B31-0523-46A9-B835-4FDD79ACFAC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5928873$A8A8C54B-7505-41AB-9618-0AB5AD27C4DB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"572a4a943383644dbb46588f76700e4b99d80377","datavalue":{"value":"1584470","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5928873$045EC6E1-6C41-47E4-8526-7438BEDFE927","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e86d9b4ad5a06064fd9c9bcbc50f8026b1c776dc","datavalue":{"value":"embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q5928873$FA42FDCB-342B-4BB8-AD0F-5DA74A21CA77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f7b4330388d7b99fc9d918a33ddb2093f78f62b","datavalue":{"value":"grids","type":"string"},"datatype":"string"},"type":"statement","id":"Q5928873$79E517E0-2F8E-4B43-97DE-EEB5D8C79F24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ada8d30f2ef08fc8cb2c5d1f7da969abbc27918a","datavalue":{"value":"dilation","type":"string"},"datatype":"string"},"type":"statement","id":"Q5928873$5A146FFD-58BD-4E7A-9B97-70C41991F3FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89a2bcf240a7d31de38c226ed25b9ba23d8a1c57","datavalue":{"value":"edge-congestion","type":"string"},"datatype":"string"},"type":"statement","id":"Q5928873$E5A5D7AF-E9D9-4C11-85DC-32820C75E486","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":"Q5928873$0C8DE82C-4047-4F9D-89FE-E05954ACDD10","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"990aae89d59ccfd43d4ff686dbf16fc7108748c2","datavalue":{"value":{"entity-type":"item","numeric-id":1893693,"id":"Q1893693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928873$4CF8FD6E-A438-4938-8AA4-936FA36C426B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cda24fa1cc84597fc35d7387e1656536c6d34516","datavalue":{"value":{"entity-type":"item","numeric-id":3950483,"id":"Q3950483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928873$E1D4EFCB-D461-4B45-9EDE-BC9436C2255F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a5e21c79f3dd7fe76f3449d5fe1009f7827392a","datavalue":{"value":{"entity-type":"item","numeric-id":4326630,"id":"Q4326630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928873$CCB66DD2-48BB-4D03-8B2E-5519A88C3053","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ddfeba75ace0f57cbf6e9428d3a2341565c57d7","datavalue":{"value":{"entity-type":"item","numeric-id":1970694,"id":"Q1970694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928873$035B7F57-87BA-453F-8948-67058C65855D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d30315f34cd8ca007635cf42b8eec14c3225877","datavalue":{"value":{"entity-type":"item","numeric-id":807642,"id":"Q807642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928873$76567338-1FBB-4D67-AD9E-D352747565EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a51a4833ab61aaf6edfafd3d97421e3449c5965","datavalue":{"value":{"entity-type":"item","numeric-id":3357515,"id":"Q3357515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928873$8186A48A-AD0C-47E5-95C9-2AC1414F972D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a03df6159403f8e2819b21b8def7de9a2c76af59","datavalue":{"value":{"entity-type":"item","numeric-id":1214948,"id":"Q1214948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928873$83C651CA-1E2A-4AF1-B643-C3E2149F7DE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a04ea4af01bb57e3ae9aa547182c1fd25f323787","datavalue":{"value":{"entity-type":"item","numeric-id":4887729,"id":"Q4887729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928873$13F6466F-D23F-465B-BEE9-9199AF25B9F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9dc2ae67caa4232288e8640bda8a06225eddac86","datavalue":{"value":{"entity-type":"item","numeric-id":5541108,"id":"Q5541108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928873$31BEEB68-9904-4230-9C2D-887C24E7ADC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55d2d9283908cf8afdce0d0f4d742097fbb72bc7","datavalue":{"value":{"entity-type":"item","numeric-id":1920427,"id":"Q1920427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928873$E69F13B6-B555-4685-86C9-0AC6CAD00F40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3e3e64404b4cf01890dbc18406480e79d011ce2","datavalue":{"value":{"entity-type":"item","numeric-id":287153,"id":"Q287153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928873$F68DB036-7773-49DF-B364-9FB6365A4E57","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":"Q5928873$C3FCA62C-9A10-4948-874F-10494A4985F2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c623bbaea576b039ae82750b592881907f25b59c","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(00)00224-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q5928873$F030AE1A-C958-43F8-824B-EFEB0D67BDE1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"78628b6e7f94c456e7d88a40dead09d32a73b603","datavalue":{"value":"W2049129900","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5928873$5918EEB1-5EF3-4C29-B299-FCE6A1E9E974","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"48984909f6f79e854d1aa9643914c5a2615cabd2","datavalue":{"value":"An embedding of a graph \\(G\\) into a graph \\(H\\) is a pair of two mappings: an injection \\(\\phi:V_G\\mapsto V_H\\) and a routing scheme that maps \\(E_G\\) into the set of paths in \\(H\\). The authors consider two embedding parameters: dilation, defined as the length of a longest path in the image of the routing scheme, and the edge-congestion, defined as the maximum over \\(e\\in E_H\\) of the number of paths in the image of the routing scheme that contain \\(e\\). NEWLINENEWLINENEWLINEThe authors construct embeddings of 2-dimensional \\(h\\times w\\) grids into \\(h'\\times w'\\) grids (with \\(h'w'\\geq hw\\)) which are optimal with respect to the dilation or edge-congestion. The situation depends on two cases: \\(h'<h\\leq w<w'\\) and \\(h<h'\\leq w'<w\\). In the first case a lower bound for the dilation has been derived that matches a known constructive upper bound. A new construction provides an embedding with the edge-congestion that might exceed the optimal one at most by one. The lower bounds for the involved parameters are based on graph isoperimetric problems. NEWLINENEWLINENEWLINEIn the second case new constructions provide embeddings with dilation at most 5 and edge-congestion at most 4. In many cases the edge-congestion can be lowered down to 2 or to 3.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5928873$1BA4BBB1-B7D0-4658-BCE1-6C60024F2B2B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3241670c8b31925653b9b130a6ee65d7a408ec87","datavalue":{"value":{"entity-type":"item","numeric-id":4232793,"id":"Q4232793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1caab532b92c6f93cba64cec1b65205c0da4417a","datavalue":{"value":{"amount":"+0.9247288107872008","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":"Q5928873$BC2A5DD9-99C1-4988-A2AB-08B5B07C1A70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6dae8bb0c63abdd4bdf5e69a7baea02fb4f1dd2","datavalue":{"value":{"entity-type":"item","numeric-id":3798267,"id":"Q3798267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3aacaf0488539f09fa8ccd01316e1b8902a9b84b","datavalue":{"value":{"amount":"+0.8531330227851868","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":"Q5928873$F6B0EDD2-63B7-4484-A7B5-7DB714D3C55A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a02c4f0e427d47fc20a07cb0b16f3c0d978b6fc9","datavalue":{"value":{"entity-type":"item","numeric-id":4706198,"id":"Q4706198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c126bcc75d9c1c0092370aeb2575235e47cdad85","datavalue":{"value":{"amount":"+0.850456178188324","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":"Q5928873$7C7CA353-2ADE-4864-ADD9-6BF2F10F4D80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7193317500148366af4e453d030faf87ec766a24","datavalue":{"value":{"entity-type":"item","numeric-id":4887729,"id":"Q4887729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a190124558189a24a9479462a2a97f29c3b0b81","datavalue":{"value":{"amount":"+0.8497337102890015","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":"Q5928873$B2C13BE5-16D6-48E6-B9CC-1E643AAD4C0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a7b5eda77f457ca64f977b03eb24cb25e27728f","datavalue":{"value":{"entity-type":"item","numeric-id":740976,"id":"Q740976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6bc627c532a3b4c46039e2766117acfb8e636e67","datavalue":{"value":{"amount":"+0.8283907771110535","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":"Q5928873$63A83368-842D-4B9C-9C08-94EEBCA6CD49","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5928873","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5928873"}}}}}