You are not logged in | Log in

2,1)-labeling of unit disk intersection graphs

Speaker(s)
Konstanty Junosza-Szaniawski
Affiliation
Politechnika Warszawska
Date
March 9, 2017, 12:15 p.m.
Room
room 5870
Seminar
Seminar Algorithms

We give a family of online algorithms for the classical coloring and the L(2,1)-labeling problems of unit disk intersection graphs. In the L(2,1)-labeling we ask for an assignment of non-negative integers to the vertices of the input graph, such that adjacent vertices get labels that differ by at least 2, and vertices with a common neighbor get different labels.
In particular, we present a coloring algorithm with competitive ratio less than 5, what makes it the currently best online coloring algorithm for unit disk intersection  graphs. Our algorithms make use of a geometric representation of such graphs and are inspired by previous results, but have better competitive ratios.  The improvement comes from a novel application of a  fractional and a b-fold coloring of the plane, which is in turn  a variation of the Hadwiger-Nelson problem. Our method can also be adapted successfully for other classes of geometric intersection graphs.