Optimizing regular edge labelings

Sander Verdonschot

A rectangular cartogram is a type of map that visualizes a quantity of a region, for example population, by representing the region as a rectangle with area proportional to this quantity. To keep the map recognizable, it should preserve key features of the geometric map, like adjacencies and relative position of the regions. The adjacencies and their directions are typically given by means of a regular edge labeling of the dual graph of the input map. We present a lower- and upperbound on the number of regular edge labelings a given graph can have and show how to find near-optimal regular edge labelings for various quality criteria.