Hypermedia Synchronization and Series-Parallel Graphs

The actual formats used to publish documents on the Internet bring, without discussion, new facilities compared to the paper material, because of their interactivity capabilities and their integration of multimedia. But needs are still growing and new languages appear regularly, attempting to improve the structure and the interactivity of documents. Among these languages, some like SMIL (Synchronized Multimedia Integration Language) offer the possibility of animating and synchronizing media components in documents.

The variety of components that form a document (audio, video, text, image...) makes the animation a difficult problem. The author of a synchronized document provides a set of temporal constraints to describe the progress of the presentation. Each of these components has a duration of presentation that is flexible within some boundaries. The problem consists in finding a good adjustment of the durations so the presentation progresses as close as possible to what the author wants with avoiding any pause.

The problem can be modeled, after some restrictions, as a minimum cost tension problem in a graph. To solve it, we studied several methods of which we propose a summary and comparisons on both theoretical and practical aspects. However, the numerical tests were performed on completely random graphs.

The graphs representing the temporal constraints are in fact very structured and very close to a class of graphs called series-parallel. We show first, through numerical results, that the methods already proposed are not always very efficient. Hence, we present an adapted method that we call aggregation. But the series-parallel graphs, although very close to the real cases, are still an idealization. We finish then by presenting first results obtained for disrupted series-parallel graphs.