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

SOULIGNAC, FRANCISCO J.

Journal of Graph Algorithms and Applications

Brown University

Año: 2017 vol. 21 p. 491 - 525

This is the second and last chapter of a work in which we consider the unrestricted, minimal, and bounded representation problems for unit interval (UIG) and unit circular-arc (UCA) graphs. In the unrestricted version (REP), a proper circular-arc (PCA) model M is given and the goal is to obtain an equivalent UCA model U. In the bounded version (BOUNDREP), M is given together with some lower and upper bounds that the beginning points of U must satisfy. In the minimal version (MINUCA), the circumference of the circle and the length of the arcs in U must be simultaneously as small as possible, while the separation of the extremes is greater than a given threshold. In this chapter we take advantage of the theoretical framework developed in Chapter I to design efficient algorithms for these problems. We show a linear-time algorithm with negative certification for REP, that can also be implemented to run in logspace. We develop algorithms for different versions of BOUNDREP that run in linear space and quadratic time. Regarding MINUCA, we first show that the previous linear-time algorithm for MINUIG (i.e., MINUCA on UIG models) fails to provide a minimal model for some input graphs. We fix this algorithm but, unfortunately, it runs in linear space and quadratic time. Then, we apply the algorithms for MINUIG and MINUCA (Chapter I) to find the minimum powers of paths and cycles that contain given UIG and UCA models, respectively.