Proportional Contact Representations of Planar Graphs

Alam, Muhammed Jawaherul and Biedl, Therese and Felsner, Stefan and Kaufmann, Michael and Kobourov, Stephen G. (2012) Proportional Contact Representations of Planar Graphs. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011 , pp. 26-38(Official URL:

Full text not available from this repository.


We study contact representations for planar graphs, with vertices represented by simple polygons and adjacencies represented by point-contacts or side-contacts between the corresponding polygons. Specifically, we consider proportional contact representations, where pre-specified vertex weights must be represented by the areas of the corresponding polygons. Several natural optimization goals for such representations include minimizing the complexity of the polygons, the cartographic error, and the unused area. We describe constructive algorithms for proportional contact representations with optimal complexity for general planar graphs and planar 2-segment graphs, which include maximal outerplanar graphs and partial 2-trees.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-25878-7_4
Classifications: M Methods > M.600 Planar
Z Theory > Z.500 Representations

Actions (login required)

View Item View Item