Paper Info
Title
Linear-time algorithms for hole-free rectilinear proportional contact graph representations
Abstract
In a proportional contact representation of a planar graph, each vertex is represented by a simple polygon with area proportional to a given weight, and edges are represented by adjacencies between the corresponding pairs of polygons. In this paper we study proportional contact representations that use rectilinear polygons without wasted areas (white space). In this setting, the best known algorithm for proportional contact representation of a maximal planar graph uses 12-sided rectilinear polygons and takes O(nlogn) time. We describe a new algorithm that guarantees 10-sided rectilinear polygons and runs in O(n) time. We also describe a linear-time algorithm for proportional contact representation of planar 3-trees with 8-sided rectilinear polygons and show that this is optimal, as there exist planar 3-trees that require 8-sided polygons. Finally, we show that a maximal outer-planar graph admits a proportional contact representation using rectilinear polygons with 6 sides when the outer-boundary is a rectangle and with 4 sides otherwise.
Year
DOI
Venue
2013
10.1007/978-3-642-25591-5_30
Algorithmica
Keywords
DocType
Volume
Graph drawing,Contact representation,Cartogram,Planar graph,Polygon
Journal
67
Issue
ISSN
Citations 
1
0178-4617
7
PageRank 
References 
Authors
0.48
26
6
Name
Order
Citations
PageRank
Muhammad Jawaherul Alam1142.65
Therese Biedl2902106.36
Stefan Felsner369272.23
Andreas Gerasch41429.42
Michael Kaufmann536125.45
Stephen G. Kobourov61440122.20