Graph decompositions and Unit Disk Graphs

Sudeshna Kolay 

Assistant Professor

IIT Kharagpur

ABSTRACT

Often an intractable problem for general graphs becomes tractable for a special class of graphs due to their additional structural properties. Unit disk graphs are a special class of graphs derived from layouts of unit disks in the 2-dimensional plane. For most well-known problems, unit disk graphs have much better tractability results than general graphs - many of these algorithms use tree decompositions of unit disk graphs or derived graphs from unit disk graphs to achieve better running times. We shall see three such applications of tree decomposition algorithms on unit disk graphs.