Recognizing Weighted Disk Contact GraphsKlemz, Boris and Nöllenburg, Martin and Prutkin, Roman (2015) Recognizing Weighted Disk Contact Graphs. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 2426, 2015 , pp. 433446(Official URL: http://dx.doi.org/10.1007/9783319272610_36). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319272610_36
AbstractDisk contact representations realize graphs by mapping vertices bijectively to interiordisjoint disks in the plane such that two disks touch each other if and only if the corresponding vertices are adjacent in the graph. Deciding whether a vertexweighted planar graph can be realized such that the disks’ radii coincide with the vertex weights is known to be NPhard. In this work, we reduce the gap between hardness and tractability by analyzing the problem for special graph classes. We show that it remains NPhard for outerplanar graphs with unit weights and for stars with arbitrary weights, strengthening the previous hardness results. On the positive side, we present constructive lineartime recognition algorithms for caterpillars with unit weights and for embedded stars with arbitrary weights.
Actions (login required)
