Open questions • Approximating Minimum Connected Dominating Set in disk graphs?

distributed algorithms? Model for wireless networks • Devices are points in the plane • Together with radio range defines disks • Induces graph structure: disk graph (DG) • Vertex per device, edge if disks intersect • All devices equal: unit disk graph (UDG) • Polynomial time approx. schemes (PTAS) Connected dominating sets • Backbone for network communication • Each disk has neighbor in or is in CDS • CDS induces connected graph • For UDGs: PTAS using shifting technique • Partition plane into squares • Optimize per square using treewidth-boun