Home  Issues  Aims and Scope  Instructions for Authors 
Special Issue on Selected Papers from the Twentieth International Symposium on Graph Drawing, GD 2012
DOI: 10.7155/jgaa.00299
Edgeweighted contact representations of planar graphs
Vol. 17, no. 4, pp. 441473, 2013. Regular paper.
Abstract We study contact representations of edgeweighted planar graphs, where vertices are represented as interiordisjoint rectangles or rectilinear polygons and edges are represented as contacts of vertex boundaries whose contact lengths represent the edge weights. For the case of rectangles, we show that, for any given edgeweighted planar graph whose outer face is a quadrangle, that is internally triangulated and that has no separating triangles, we can construct in linear time an edgeproportional rectangular dual (contact lengths are equal to the given edge weights and the union of all rectangles is again a rectangle) or report failure if none exists. In the case of arbitrarily many outer vertices, we show that deciding whether a square layout exists is NPcomplete. If the orientation of each contact is specified by a socalled regular edge labeling and edge weights are lower bounds on the contact lengths, a corresponding rectangular dual that minimizes the area and perimeter of the enclosing rectangle can be found in linear time. On the other hand, without a given regular edge labeling, the same problem is NPcomplete, as is the question whether a rectangular dual exists given lower and upper bounds on the contact lengths. For the case of rectilinear polygons, we give a complete characterization of the polygon complexity required for representing connected internally triangulated graphs: For outerplanar graphs and graphs with a single inner vertex polygon, complexity 8 is sufficient and necessary, and for graphs with two adjacent or multiple nonadjacent internal vertices the required polygon complexity is unbounded.

Submitted: December 2012.
Reviewed: April 2013.
Revised: April 2013.
Accepted: June 2013.
Final: July 2013.
Published: July 2013.
