{"entities":{"Q1805444":{"pageid":1816186,"ns":120,"title":"Item:Q1805444","lastrevid":46357869,"modified":"2025-12-24T15:26:05Z","type":"item","id":"Q1805444","labels":{"en":{"language":"en","value":"Short encodings of planar graphs and maps"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 756150"}},"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":"Q1805444$B44256B0-94DD-4BA5-931D-7E988D57BD42","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f9fc419506fc3df997605a145790bd5082becb98","datavalue":{"value":{"text":"Short encodings of planar graphs and maps","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1805444$87DF35E9-5DD9-4622-9241-547B8171950B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0129602f731748a722a6d5e709c2c80a7104312a","datavalue":{"value":"0833.05025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805444$69BA9C40-30E9-411A-A91F-21073FCAEC2C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"61549769af3ac5fbf550aa3cdc9499b686345d70","datavalue":{"value":"10.1016/0166-218X(93)E0150-W","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805444$45C80488-F01F-49BE-8E9C-552F74B9FB01","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"feffac0caf6379a697d486697a183fca225cced3","datavalue":{"value":{"entity-type":"item","numeric-id":1805443,"id":"Q1805443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805444$8ADB95BD-2DBD-4331-8F99-D7E8A641B8BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7bff508e7a535256da6776295a5a965111663706","datavalue":{"value":{"entity-type":"item","numeric-id":672392,"id":"Q672392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805444$D3D7EB6B-CF75-4CF7-94EC-87D5F95B8BBC","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":"Q1805444$26D1941D-1143-45D1-9DBC-96FA6FEF8ADF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3da5740e8a0078651a07b58d85e873b362b3e452","datavalue":{"value":{"time":"+1996-03-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1805444$26CC2FCE-2060-48D1-A693-0C4DFDF02BDE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fd3fcef6166e256c6ff922d5d79b122f7fd9d3da","datavalue":{"value":"The authors give space-efficient binary encoding and decoding algorithms for several classes of unlabelled planar graphs and maps, which run in linear time and provide the most compact encoding. They construct a particular depth-first search tree of a map and sequentially delete the non-tree edges and add one-bit labels. This converts the map into a labelled version of the search tree. The tree is encoded in any standard way. In this way, they obtain: A loop- and stick-free map with \\(m\\) edges can be encoded in \\(3m+ O(1)\\) bits. An arbitrary planar graph with \\(m\\) edges can be encoded in \\(m\\text{ lg } 12+ O(1)\\) bits.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1805444$69421271-392D-41C8-9987-54C9D8FE1F13","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5a15ba5cd77ddbb51ae11ed560267e558bda35d1","datavalue":{"value":{"entity-type":"item","numeric-id":201638,"id":"Q201638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805444$700707A2-3E12-4187-9DF7-B59CFB55B821","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805444$C1433337-970D-41F7-A4B4-7E6F4E245472","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805444$183180D5-457A-4675-B8C8-C8C50A105A70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805444$55720314-EFB9-4F45-958F-4658BD8EDB51","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2761dca9cdd21e232d1e4cebf9dedb6f503edd27","datavalue":{"value":"756150","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805444$0FF23A7F-8CDA-4565-9679-90F4ED14C3E8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"86858b19e06e7f53cefb9a2372bf5b13d0adff66","datavalue":{"value":"encoding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1805444$F2DE738F-BA36-44CA-A3EB-2141A1C0976E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fdd265674d6df629203f536a9a68808a13f0def8","datavalue":{"value":"decoding algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1805444$06491986-4B80-4C4D-87E0-C1E9A1D540F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a602521768d4795b8ce801eaf970fa00075370dd","datavalue":{"value":"planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1805444$27BFC949-82EC-4503-BC51-C9C81420A71A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1dd540b45bafcf7db37d1e4a03cbbfc1754b67b","datavalue":{"value":"maps","type":"string"},"datatype":"string"},"type":"statement","id":"Q1805444$6E554C52-CDEE-4727-9D30-A69217294408","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7aa00a4c4635da3e1a8927a353052773fcbd5326","datavalue":{"value":"depth-first search tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1805444$14B9D0F4-4EC7-47C5-8406-ED6469B620D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de7680ae9346bf7be9bf2087d0fbd5cbb5596fde","datavalue":{"value":"labels","type":"string"},"datatype":"string"},"type":"statement","id":"Q1805444$73D552F9-2B47-41D7-A98E-3AE2EB212C2D","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":"Q1805444$F9EC791B-85F9-4197-A7F5-72A5D4DC3E9C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9914f8121a32baf6895c6797ec99c63c32102968","datavalue":{"value":{"entity-type":"item","numeric-id":1242450,"id":"Q1242450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805444$6209855F-F796-46D3-B0AE-A18CD4947BF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44e85ba57e9ab8eefde4f3b7c1b1ce77ed79d631","datavalue":{"value":{"entity-type":"item","numeric-id":4053461,"id":"Q4053461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805444$DFF91D4B-DBBF-4495-95FC-223C8B569384","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805444$B098114E-27A7-468E-9C5F-45FA087C9C0A","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":"Q1805444$B3AD817F-184E-49CC-8241-1C773D2CD83B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9c44edac21a5ab02be94c02fc7a49aa079a2336","datavalue":{"value":{"entity-type":"item","numeric-id":1157966,"id":"Q1157966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805444$904FA68E-1734-467A-B3F7-B54E0BBCF352","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3ca3c6ba1834ed0aadd35eb1abcfa4835f5b2c9","datavalue":{"value":{"entity-type":"item","numeric-id":2277480,"id":"Q2277480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805444$F8B8A3FF-E7A2-4654-8675-694AD2DD4617","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":"Q1805444$5C9DFDC4-E440-4894-92EE-75F831BEE69A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dfeb2e154fb465d9b0b8596ac60f7d89bfb50593","datavalue":{"value":{"entity-type":"item","numeric-id":800734,"id":"Q800734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805444$E658DA22-275F-40D6-B27D-DA463BD812D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1702dbbf3d37ffe7da1b08f854ae6de4d22b675e","datavalue":{"value":{"entity-type":"item","numeric-id":3287780,"id":"Q3287780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805444$F0AC2724-3A36-44F5-9503-24C5369C8722","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75f9fde64ef05ada3bd5b496b2bc1643f073454f","datavalue":{"value":{"entity-type":"item","numeric-id":5723653,"id":"Q5723653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805444$E7C0DFF2-62C8-4582-8B19-2B7B2A94E842","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"4970af2123e97a7ab682a1ef987cfc125483f9f8","datavalue":{"value":"Q127570257","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805444$41A6BAA3-11F5-4F17-B28A-D62DA659A5FE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c276c80ac7a1012913715e1a2719fd6c4cc03741","datavalue":{"value":"https://doi.org/10.1016/0166-218x(93)e0150-w","type":"string"},"datatype":"url"},"type":"statement","id":"Q1805444$B6EBAD1A-76AF-4272-B080-602024DD453A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c759496ce8c04131388352128a1a35897c537b6c","datavalue":{"value":"W2010356699","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805444$F543B004-DDC6-4637-8C91-4653D1EFFD3B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"42da7c30afe7fea3b2cc56040a75eee9aece05d5","datavalue":{"value":{"entity-type":"item","numeric-id":800734,"id":"Q800734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dbd09df4ead55364f717b4c04e42a4649c791f81","datavalue":{"value":{"amount":"+0.872542679309845","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":"Q1805444$D362C6F6-CD3B-4037-8F69-5EF1A4CCC90D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30d8ad90714204075b1e8ca48febb57f05dd1f37","datavalue":{"value":{"entity-type":"item","numeric-id":2502033,"id":"Q2502033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8b49ab4878004408f6f00e4ee45f6b25a955bd3","datavalue":{"value":{"amount":"+0.8641217947006226","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":"Q1805444$3F29E98B-6FA3-4375-888E-B63D32BDC8EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c118c40c6e86ca2fd9b4267853e4ffd6cc011a2","datavalue":{"value":{"entity-type":"item","numeric-id":5710808,"id":"Q5710808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25c1e7dc824703a4646c089094c49b522d452290","datavalue":{"value":{"amount":"+0.8593431711196899","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":"Q1805444$DA8439AE-8149-421C-BA89-604CE5B70EAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00141ee64e5b46a5a8005dd2419a0ad814034ef3","datavalue":{"value":{"entity-type":"item","numeric-id":4699160,"id":"Q4699160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c8a2fc3c8f12a9ca9abe22d8971d6a84f3f9363","datavalue":{"value":{"amount":"+0.8590266108512878","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":"Q1805444$59A66EDB-35C2-4CCE-AA68-20D125732F4E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1805444","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1805444"}}}}}