{"entities":{"Q800734":{"pageid":802582,"ns":120,"title":"Item:Q800734","lastrevid":64469196,"modified":"2026-04-11T20:04:51Z","type":"item","id":"Q800734","labels":{"en":{"language":"en","value":"On the succinct representation of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3878377"}},"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":"Q800734$09F5B4E7-42E0-4612-929B-8FBCC5FD5809","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ca8a287afeff6d229953805cb3295f6c33229224","datavalue":{"value":{"text":"On the succinct representation of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q800734$2AEAC599-545A-4D8A-A341-E20359D1B6CC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a4734800badc661bc6f628e85cf8932e0f2d3bf1","datavalue":{"value":"0551.68059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800734$2B62526B-9855-425D-AEA7-658AC7C7818A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"588da9ef5371bc059c28a2b52bd0c57cbf0c9610","datavalue":{"value":"10.1016/0166-218X(84)90126-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800734$D8E31236-31F0-405E-A5E3-467AD82C7068","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c66a437d74ae466cacad614cef92f8e5d71204e6","datavalue":{"value":{"entity-type":"item","numeric-id":239429,"id":"Q239429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800734$1BC3A70F-E6A9-4759-8AC3-ECBF1E1BBA12","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":"Q800734$95D9BA65-AF18-4C9F-A71A-11075EC83989","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q800734$F7388A20-3FC0-41E4-A3B9-9F20104436E0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6005cb08ed54d519eddef806d76593d3167c8650","datavalue":{"value":"Let \\({\\mathcal G}_ be\\) a class of (labeled or unlabeled) graphs and \\({\\mathcal G}_ n\\) be the class of graphs in \\({\\mathcal G}\\) having n vertices. The problem discussed is the following: find a representation (or encoding) of graphs in \\({\\mathcal G}\\) which is succinct (i.e. the length of the encoding of \\(G\\in {\\mathcal G}_ n\\) is not too large compared with the lower bound \\(\\log_ 2| {\\mathcal G}_ n|)\\) and efficiently (e.g. polynomial time) computable. The paper considers the case of planar graphs. An encoding using at most 12n bits is given for the unlabeled case and (improving a result of \\textit{A. Itai} and \\textit{M. Rodeh} [Acta Inf. 17, 215-219 (1982; Zbl 0471.68042)]), an asymptotically optimal encoding using \\(n\\lceil \\log_ 2n\\rceil +12n\\) bits is given for the labeled case.","type":"string"},"datatype":"string"},"type":"statement","id":"Q800734$58E85522-B4A6-45CF-9DD8-2326479703DB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800734$D4A47307-23D5-45F0-8D70-C5BF0E1E9A04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800734$EE80FDDD-93B9-40C0-A050-99BEF1BC1F8B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7cd3d44fdd85a5ea71566dcd1a513620186980ac","datavalue":{"value":"3878377","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800734$CA3153DD-ABEC-4ED6-987A-3FE057147191","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c95518f0897c0c624f62c514cb59b08a408d3443","datavalue":{"value":"encoding of graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q800734$0907DE38-3DC4-4653-87A9-AE93B40C12D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a602521768d4795b8ce801eaf970fa00075370dd","datavalue":{"value":"planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q800734$2E603B3A-A50F-42C7-BA75-0F19D1C674B9","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":"Q800734$F0970CA8-E346-4024-BCFD-038690E64BCA","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"086bb2c71ee83e5078119da67c2b7932b5461b73","datavalue":{"value":"Q56209828","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800734$46A0C494-19FC-4F50-835B-95360D0B3011","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"51617bdd59c74a817347eb18a12da68a22d46f80","datavalue":{"value":{"entity-type":"item","numeric-id":2558231,"id":"Q2558231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800734$E9E3A29E-A301-4FDF-943A-58AB911B6F3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cff90b53746deaf40f0bd975035788d645dc76ab","datavalue":{"value":{"entity-type":"item","numeric-id":5682013,"id":"Q5682013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800734$E00A1085-E0B8-4631-AA67-491A077ADC95","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":"Q800734$E19C3774-274F-4137-BDCB-8403BEDD5D34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a8d2cc4cca4b3bb968e63d1446e69d34aeea62a","datavalue":{"value":{"entity-type":"item","numeric-id":4125770,"id":"Q4125770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800734$D1876A3D-FB29-401C-BBEF-2D806207670E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac0ec4868dba1b37d1adb8bb9f6a23d6c0a862f5","datavalue":{"value":{"entity-type":"item","numeric-id":3880849,"id":"Q3880849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800734$D44B2CDD-5A53-4575-9A38-953483280A3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"040b7b9fbede4032e8348103c4d815e16fc87c56","datavalue":{"value":{"entity-type":"item","numeric-id":4075503,"id":"Q4075503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800734$EAE831D5-08F0-4D70-94E6-9B63B899C18D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68c516460706e34bfacf776c096f40a576fd2116","datavalue":{"value":{"entity-type":"item","numeric-id":600247,"id":"Q600247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800734$B565A0DB-2EFA-451E-AE62-D8FAB19C96EE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3b061c74e155d49de69a51bc0e560e434f44cf1","datavalue":{"value":{"entity-type":"item","numeric-id":4725746,"id":"Q4725746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89b5413f6b58a4f31c484f20db8413b88955c3af","datavalue":{"value":{"amount":"+0.9749298","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q800734$E20A4B84-AED8-4161-83BB-6AC3DE51BFC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c786313cafd54cab59446ecc70225d04da3f676","datavalue":{"value":{"entity-type":"item","numeric-id":3325058,"id":"Q3325058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b46285343a162edc9d21112841fe38f43ed2e52","datavalue":{"value":{"amount":"+0.9725629","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q800734$B67509BA-B9C7-4136-B88D-2C3D28BEC482","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31810063dc32bd4e4b9f8a1f8a02b0fe16d88985","datavalue":{"value":{"entity-type":"item","numeric-id":3541102,"id":"Q3541102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c9c7a3b07501bc07df329f5cbfc43c5e8c7155f0","datavalue":{"value":{"amount":"+0.9693251","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q800734$5D0F4CB9-A0BA-4772-A7EE-3F1C7A477D07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e42d5602adb43e3b1d7c630e612358bc8855879b","datavalue":{"value":{"entity-type":"item","numeric-id":3575243,"id":"Q3575243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7543967ecbd13f28cd31a115bf58382c9fd080f9","datavalue":{"value":{"amount":"+0.94266546","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q800734$E9710741-0AD1-45E1-BAF8-C977AB771717","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c0d3767b1f48f2b480379a2c5bc976c72d77951","datavalue":{"value":{"entity-type":"item","numeric-id":2428673,"id":"Q2428673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d6cfe74c6eb93a50a0bc051ec02c56c269eeb9a","datavalue":{"value":{"amount":"+0.93648374","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q800734$907F8459-29A6-4EF9-9B83-2B3B2F5F5DE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff1c88b42161c8299675515f09feb4a8f7ccbc9a","datavalue":{"value":{"entity-type":"item","numeric-id":5387767,"id":"Q5387767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d0d7323bfaeb29ee229fd3df07625fba1969055","datavalue":{"value":{"amount":"+0.9364835","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q800734$7F67CAC4-A0D1-43F5-84B6-1042F28846A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99abbf996b01c3753029ef90c670b6a080dcb66a","datavalue":{"value":{"entity-type":"item","numeric-id":4694758,"id":"Q4694758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3799ae9a6cecd2f626c2f64ab1db7f1f9ba1ffd0","datavalue":{"value":{"amount":"+0.9336927","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q800734$97C93576-4C65-45C5-ADFF-30DAE8D9BB01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc5e1bbc1fcbf88e50fc65a51c734138550c1cc1","datavalue":{"value":{"entity-type":"item","numeric-id":391972,"id":"Q391972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"260e3c31d9e9159dbe97cbafb1fe09de7dfd390f","datavalue":{"value":{"amount":"+0.92406934","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q800734$DF8EDFDE-75C6-4DA4-8A00-1AAF2606B840","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c40d3f2467561f7661d3c246ed2b71c444a51d9","datavalue":{"value":{"entity-type":"item","numeric-id":4645179,"id":"Q4645179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fac941dd248a37f41db67ea3f0d56d15039aca53","datavalue":{"value":{"amount":"+0.91890645","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q800734$9BB1629E-698C-40D2-8F65-4FC8F369B3FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4143fce2e162f69499af3e5b302ee877a6db98f5","datavalue":{"value":{"entity-type":"item","numeric-id":3833618,"id":"Q3833618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"efc2a76c6cd81dfc24339fa0b5b5fe27223ff335","datavalue":{"value":{"amount":"+0.9188076","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q800734$4253A748-1F67-4CFC-8721-C7FA39FEAB5B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the succinct representation of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_succinct_representation_of_graphs"}}}}}