Wireless communication graphs

We consider graph models which represent communication in wireless ad-hoc networks. In such networks, each node equipped with a radio has a certain transmission range, and all surrounding nodes in this range can receive a transmission. In ideal settings, this transmission range creates a circular disk around each node, so that disk intersection graphs are common models. We review some properties of these disk graphs and introduce more realistic and sophisticated geometric graphs to model wireless communication. These models are explored and exploited to obtain approximability results for two important problems, maximum independent sets and minimum dominating sets. Although these more realistic models have less structure, the same complexity status as for disk graphs can be achieved. Furthermore, we present simple, constant factor approximation algorithms for the problems that run locally in each node, and that do not rely on positional information, making them independent of localization.