I en rektilinjär dual av en planar graf hörn representeras av enkla rektilinjära polygoner, medan kanter representeras av sidokontakt mellan motsvarande polygoner. En rektilinjär dubbel kallas ett kartogram om arean i varje region är lika med en förspecificerad vikt. Komplexiteten hos ett kartogram bestäms av det maximala antalet hörn (eller sidor) som krävs för en polygon. I en serie av papper har den polygonala komplexiteten hos sådana representationer för maximal planar grafer minskats från de ursprungliga 40 till 34, sedan till 12 och mycket nyligen till de för närvarande mest kända 10. Här beskriver vi en konstruktion med 8-sidiga polygoner, vilket är optimalt i termer av polygonisk komplexitet eftersom 8-sidiga polygoner ibland är nödvändiga. Specifikt visar vi hur man beräknar den kombinatoriska strukturen och hur man förfinar den till en areauniversal rektangulär layout i linjär tid. Den exakta kartogrammet kan beräknas från område-universal layout med numerisk iteration, eller kan approximeras med en kuperad heuristisk. Vi beskriver också en alternativ konstruktion av kartogram för Hamiltonian maximal plana grafer, vilket gör att vi direkt kan beräkna kartogram i linjär tid. Dessutom bevisar vi att även för Hamiltonian grafer 8-sidiga rektilinjära polygoner är nödvändiga, genom att konstruera en icke-trivial lägre bundna exempel. Komplexiteten i kartogram kan reduceras till 6 om Hamiltons väg har den extra prop- * Forskning initierad på Dagstuhl 10461 om schemaläggning † Finansieras delvis av NSF bidrag CCF-0545743 och CCF-1115971  och forskning som stöds av NSERC. § Finansieras delvis: EURGIGA-projektet GraDR & DFG Fe 340/7-2 ¶ Delvis stödd av EURGIGA-projektet GraDR Tillstånd att göra digitala eller papperskopior av hela eller delar av detta arbete för personligt eller klassrumsbruk beviljas utan avgift under förutsättning att kopior inte görs eller distribueras för vinst eller kommersiell fördel och att kopiorna bär detta meddelande och den fullständiga hänvisningen på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. SCG '12, 17-20 juni 2012, Chapel Hill, North Carolina, USA. Copyright 2012 ACM 978-1-4503-1299 erty att det är enbent, som i yttre plana grafer. Således har vi optimala representationer (i termer av både polygonal komplexitet och körtid) för Hamiltonian maximal planar och maximal yttre plana grafer.
I den allmänna rectilinear inställningen har det nyligen visat sig att 8 sidor ibland är nödvändiga och alltid tillräckligt för en rectilinear cartogram av maximal planar grafer REF.
Computing cartograms with optimal complexity
{'venue': "SoCG '12", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}