Home Issues About JGAA Instructions for Authors
 
 
Special Issue on Selected Papers from the Nineteenth International Symposium on Graph Drawing, GD 2011
DOI: 10.7155/jgaa.00276
Proportional Contact Representations of Planar Graphs
Md. Jawaherul Alam, Therese Biedl, Stefan Felsner, Michael Kaufmann, and Stephen G. Kobourov
Vol. 16, no. 3, pp. 701-728, 2012. Regular paper.
Abstract 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. Natural optimization goals for such representations include minimizing the complexity of the polygons, and the unused area. We describe algorithms for proportional contact representations with optimal polygonal complexity for general planar graphs and planar 2-segment graphs, which include maximal outer-planar graphs and partial 2-trees.
Submitted: November 2011.
Reviewed: April 2012.
Revised: May 2012.
Reviewed: July 2012.
Revised: August 2012.
Accepted: August 2012.
Final: September 2012.
Published: September 2012.
Communicated by Marc J. van Kreveld and Bettina Speckmann
article (PDF)
BibTeX