Recognizing Weighted Disk Contact Graphs

Klemz, 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 24-26, 2015 , pp. 433-446(Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_36).

Full text not available from this repository.

Abstract

Disk contact representations realize graphs by mapping vertices bijectively to interior-disjoint 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 vertex-weighted planar graph can be realized such that the disks’ radii coincide with the vertex weights is known to be NP-hard. In this work, we reduce the gap between hardness and tractability by analyzing the problem for special graph classes. We show that it remains NP-hard for outerplanar graphs with unit weights and for stars with arbitrary weights, strengthening the previous hardness results. On the positive side, we present constructive linear-time recognition algorithms for caterpillars with unit weights and for embedded stars with arbitrary weights.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.560 Geometry
P Styles > P.999 Others
Z Theory > Z.250 Geometry
Z Theory > Z.500 Representations
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 04 May 2016 15:51
Last Modified: 04 May 2016 15:51
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1510

Actions (login required)

View Item View Item