Låt G = (V, E) vara en plan triangulerad graf där varje vertex tilldelas en positiv vikt. En rektilinear dual av G är en partition av en rektangel in i  en enkel rektilinear regioner, en för varje vertex, sådan att två regioner är intilliggande om och endast om motsvarande hörn är anslutna med en kant i E. En rektilinear dual kallas en cartogram om arean av varje region är lika med vikten av motsvarande vertex. Vi visar att varje vertex-viktad plan triangulerad graf G medger ett kartogram av konstant komplexitet, det vill säga ett kartogram där antalet hörn i varje region är konstant. Dessutom kan ett sådant rektilinjärt kartogram konstrueras i O(n log n)-tid där n =  på V.
Även med detta extra villkor, de Berg et al. REF visar att rektolinjära kartogram med konstant regionkomplexitet kan konstrueras under O(n log n) tid.
On rectilinear duals for vertex-weighted plane graphs
{'venue': 'DISCRETE MATHEMATICS', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}