Viktor Zamaraev (Durham
A unit disk graph is the intersection graph of disks of equal
radii in the plane. The class of unit disk graphs is hereditary, and
therefore can be characterized in terms of minimal forbidden induced
subgraphs. In spite of quite an active study of unit disk graphs very
little is known about minimal forbidden induced subgraphs for this
class. We found only finitely many minimal non unit disk graphs in the
literature. In this work, we study in a systematic way forbidden
induced subgraphs for the class of unit disk graphs. We develop
several structural and geometrical tools and use them to reveal
infinitely many new minimal non unit disk graphs. Further, we use
these results to investigate the structure of co-bipartite unit disk
graphs. In particular, we give a structural characterization of those
co-bipartite unit disk graphs whose edges between the parts form a
C_4-free bipartite graph and show that bipartite complements of these
graphs are also unit disk graphs. Our results lead us to propose a
conjecture that the class of co-bipartite unit disk graphs is closed
under bipartite complementation.
Based on joint work with Aistis Atminas.
Back to the
research colloquium site.