EADS talk by Viktor Zamaraev: Forbidden induced subgraphs for unit disk graphs – Københavns Universitet

Videresend til en ven Resize Print kalender-ikon Bookmark and Share

Datalogisk Institut, DIKU > Begivenhedsmappen > Begivenheder 2017 > EADS talk by Viktor Za...

EADS talk by Viktor Zamaraev: Forbidden induced subgraphs for unit disk graphs

Title

On forbidden induced subgraphs for unit disk graphs

Abstract

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 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 tructural 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 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.