Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter II: algorithms

We consider the unrestricted, minimal, and bounded representation problems for unit interval (UIG) and unit circular-arc (UCA) graphs. In the unrestricted version, a proper circular-arc (PCA) modelM is given and the goal is to obtain an equivalent UCA model U . We show a linear time algorithm with negative certification that can also be implemented to run in logspace. In the bounded version,M is given together with some lower and upper bounds that the beginning points of U must satisfy. We develop a linear space O(n2) time algorithm for this problem. Finally, in the minimal version, the circumference of the circle and the length of the arcs in U must be simultaneously as minimum as possible. We prove that every UCA graph admits such a minimal model, and give a polynomial time algorithm to find it. We also consider the minimal representation problem for UIG graphs. As a bad result, we show that the previous linear time algorithm fails to provide a minimal model for some input graphs. We fix this algorithm but, unfortunately, it runs in linear space O(n2) time. Finally, we apply the minimal representation algorithms so as to find the minimum powers of paths and cycles that contain a given UIG and UCA models, respectively.