Proportional Contact Representations of Planar Graphs - Alam, Md. Jawaherul; Biedl, Therese; Felsner, Stefan; Kaufmann, Michael; Kobourov, Stephen (Journal of Graph Algorithms and Applications, 2012)
We study contact representations for planar graphs, with verticesrepresented by simple polygons and adjacencies represented bypoint-contacts or side-contacts between the correspondingpolygons. Specifically, we consider proportional contactrepresentations, where pre-specified vertex weights must berepresented by the areas of the corresponding polygons. Natural optimization goals for such representations include minimizingthe complexity of the polygons, and the unusedarea. We describe algorithms for proportional contactrepresentations with optimal polygonal complexity for general planar graphs and planar 2-segment graphs,which include maximal outer-planar graphs and partial 2-trees.