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

Francisco Soulignac

Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 4, pp. 491-525.

Résumé

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 (${\rm R{\small EP}}$), a proper circular-arc (PCA) model $\mathcal M$ is given and the goal is to obtain an equivalent UCA model $\mathcal U$. In the bounded version (${\rm B{\small OUND}R{\small EP}}$), $\mathcal M$ is given together with some lower and upper bounds that the beginning points of $\mathcal U$ must satisfy. In the minimal version (${\rm M{\small IN}UCA}$), the circumference of the circle and the length of the arcs in $\mathcal 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 ${\rm R{\small EP}}$, that can also be implemented to run in logspace. We develop algorithms for different versions of ${\rm B{\small OUND}R{\small EP}}$ that run in linear space and quadratic time. Regarding ${\rm M{\small IN}UCA}$, we first show that the previous linear-time algorithm for ${\rm M{\small IN}UIG}$ (i.e., ${\rm M{\small IN}UCA}$ 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 ${\rm M{\small IN}UIG}$ and ${\rm M{\small IN}UCA}$ (Chapter I) to find the minimum powers of paths and cycles that contain given UIG and UCA models, respectively.

Détail

DOI : 10.7155/jgaa.00426