Edge-Weighted Contact Representations of Planar Graphs

Nöllenburg, Martin and Prutkin, Roman and Rutter, Ignaz (2013) Edge-Weighted Contact Representations of Planar Graphs. In: 20th International Symposium, GD 2012, September 19-21, 2012 , pp. 224-235(Official URL: http://link.springer.com/chapter/10.1007/978-3-642...).

Full text not available from this repository.


We study contact representations of edge-weighted planar graphs, where vertices are rectangles or rectilinear polygons and edges are polygon contacts whose lengths represent the edge weights. 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 if one exists and report failure otherwise. For a given combinatorial structure of the contact representation and edge weights interpreted as lower bounds on the contact lengths, a corresponding contact representation that minimizes the size of the enclosing rectangle can be found in linear time.If the combinatorial structure is not fixed, we prove NP-hardness of deciding whether a contact representation with bounded contact lengths exists. Finally, we give a complete characterization of the rectilinear polygon complexity required for representing biconnected internally triangulated graphs: For outerplanar graphs complexity 8 is sufficient and necessary, and for graphs with two adjacent or multiple non-adjacent internal vertices the complexity is unbounded.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-36763-2_20
Classifications: P Styles > P.999 Others
Z Theory > Z.500 Representations
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1312

Actions (login required)

View Item View Item