Unit disk graphs are the intersection graphs of unit diameter disks in the Euclidean plane. Recognizing unit disk graph  is an important geometric problem, and has many application areas. In general, this problem is shown to be \existsR-complete. In some applications, the objects that correspond to unit disks, have predefined (geometrical) structures to be placed on. Hence, many scientists attacked this problem by restricting the domain for the centers of the disks . One example to such applications is wireless sensor networks, where each disk corresponds to a wireless sensor node, and a pair of intersecting disks correspond to a pair of sensors being able to communicate with each other . It is usually assumed that the nodes have identical sensing ranges, and thus  unit disk graph model is used to model problems concerning wireless sensor networks. In this paper, we also attack the unit disk recognition problem on a restricted domain, by assuming a scenario where the wireless sensor nodes are deployed on the corridors of a building. Based on this scenario, we impose a geometric constraint such that the unit disks must be centered onto given straight lines. We show that deciding whether there exists a realization of a given graph as unit disk graphs on straight lines is NP-hard, even if the given lines are parallel to either x-axis or y-axis. Moreover, we remark that if the straight lines are not given, then the problem becomes \exists\mathbb{R
Unit disk graphs are the intersection graphs of unit radius disks in the Euclidean plane. Deciding whether there exists an embedding of a given unit disk graph , i.e. unit disk graph recognition, is an important geometric problem, and has many application areas. In general, this problem is known to be \existsR-complete. In some applications, the objects that correspond to unit disks, have predefined (geometrical) structures to be placed on. Hence, many researchers attacked this problem by restricting the domain of the disk centers . One example to such applications is wireless sensor networks, where each disk corresponds to a wireless sensor node, and a pair of intersecting disks corresponds to a pair of sensors being able to communicate with one another . It is usually assumed that the nodes have identical sensing ranges, and thus a unit disk graph model is used to model problems concerning wireless sensor networks. We consider the unit disk graph realization problem on a restricted domain, by assuming a scenario where the wireless sensor nodes are deployed on the corridors of a building. Based on this scenario, we impose a geometric constraint such that the unit disks must be centered onto given straight lines. In this paper, we first describe a polynomial-time reduction which shows that deciding whether a graph can be realized as unit disks onto given straight lines is NP-hard, when the given lines are parallel to either x-axis or y-axis. Using the reduction we described, we also show that this problem is NP-complete when the given lines are only parallel to x-axis (and one another). We obtain those results using the idea of the logic engine introduced by Bhatt and Cosmadakis in 1987.
R
diameter
radius
R
Recognizing
Deciding whether there exists an embedding of a given
A
, i.e. unit disk graph recognition,
R
shown
known
R
scientists
researchers
R
for the centers of the disks
of the disk centers
R
correspond
corresponds
R
each other
one another
A
a
R
In this paper, we also attack
We consider
R
recognition
graph realization
R
We show
In this paper, we first describe a polynomial-time reduction which shows
R
there exists a realization of a given graph as unit disk graphs on
a graph can be realized as unit disks onto given
R
even if
when
R
Moreover, we remark that if the straight lines are not given, then the problem becomes \exists\mathbb{R
Using the reduction we described, we also show that this problem is NP-complete when the given lines are only parallel to x-axis (and one another). We obtain those results using the idea of the logic engine introduced by Bhatt and Cosmadakis in 1987.