Låt G vara en plan graf av n noder, m kanter, f ansikten, och ingen självloop. G behöver inte vara ansluten eller enkel (dvs. fri från flera kanter). Vi ger tre uppsättningar av kodningsprogram för G som alla tar O (m + n) tid för kodning och avkodning. Våra system använder sig av nya egenskaper hos kanoniska beställningar av plana grafer och nya tekniker för att bearbeta strängar av flera typer av parenteser. För applikationer som behöver bestämma i O(1) tid adjacency av två noder och graden av en nod, använder vi 2m + (5 + 1 k )n + o(m + n) bitar för alla konstant k > 0 medan den bästa tidigare bunden av Munro och Raman är 2m + 8n + o(m + n). Om G är triansluten eller triangulerad, minskar vårt antal till 2m + 3n + o(m + n) eller 2m + 2n + o(m + n) respektive. Om G är enkelt, vår bit räkna är 5 3 m + (5 + 1 k )n + o(n) för alla konstant k > 0. Om ett enkelt G också är trianslutet eller triangulerat räcker det alltså med 2m + 2n + o(n) eller 2m + n + o(n) bitar. Om endast adjacensfrågor stöds räknas biten för en allmän G och en enkel G blir 2m + 14 3 n + o(m + n) respektive 4 3 m + 5n + o(n). Om vi bara behöver rekonstruera G från dess kod, använder en enkel och triconnected G 3 log 2 3 2 m + O(1)  på 2,38m + O(1) bitar medan den bästa tidigare bunden av He, Kao och Lu är 2,84m.
Chuang m.fl. REF minskade antalet bitar till 2m + (5 + 1 k )n för varje konstant k > 0 med samma sökstöd.
Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}