Representation problems for unit interval and unit circular-arc graphs

FRANCISCO J. SOULIGNAC

Conferencia; The Canadian Discrete and Algorithmic Mathematics Conference (CANADAM 21); 2021

The last decade saw an increasing research on numerical representation problems for unit circular-arc models (UCA) and related classes.  In these problems we are given a proper circular-arc model $mathcal{M}$ and we have to find a UCA model $mathcal{U}$, related to $mathcal{M}$, that satisfies certain numerical constraints.  In the classical representation problem, for instance, we are given a proper circular-arc model and we have to find an equivalent unit circular-arc model whose extremes are all integer and have a polynomial size.  In this talk I present a common framework to efficiently solve different numerical representation problems for UCA models.