Advertisement
Published in:
2015 | OriginalPaper | Chapter
Recognizing Weighted Disk Contact Graphs
Authors : Boris Klemz, Martin Nöllenburg, Roman Prutkin
Published in: Graph Drawing and Network Visualization
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 \(\textsf {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 \(\textsf {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.