Edge-weighted contact representations of planar graphs

Abstract

We study contact representations of edge-weighted planar graphs, where vertices are represented as interior-disjoint 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 edge-weighted 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 edge-proportional 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 NP-complete. If the orientation of each contact is specified by a so-called 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 NP-complete, 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 non-adjacent internal vertices the required polygon complexity is unbounded.