Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00426
Bounded, minimal, and short representations of unit interval and unit circulararc graphs. Chapter II: algorithms
Vol. 21, no. 4, pp. 491525, 2017. Regular paper.
Abstract 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 circulararc (UCA) graphs.
In the unrestricted version (${\rm R{\small EP}}$), a proper circulararc (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 lineartime 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 lineartime 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.

Submitted: February 2016.
Reviewed: October 2016.
Revised: October 2016.
Accepted: February 2017.
Final: February 2017.
Published: April 2017.
Communicated by
Sue Whitesides

Journal Supporters
