Optimization Problems on Generalized Unit-Disk Graphs

Unit-disk graphs are a popular way to model wireless communication networks. The nodes in a unit-disk graphs are points in the plane—these points model the wireless devices—and two points are connected by an edge if the distance between the points is at most 1. Many classic optimization problems on graphs can be solved more efficiently on unit-disk graphs than on arbitrary graphs. In this project we will explore to what extend the results on unit-disk graphs can be generalized to more general settings. For example, what happens if there are obstacles that can prevent communication between devices, so that not every pair at distance at most 1 will be connected?