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, Eindhoven, The Netherlands , pp. 26-38 (Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_4).
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.
Repository Staff Only: item control page