Reconstruction Method for the Hypermedia Synchronization of SP-Graphs

The actual formats used to publish documents on the Internet bring, without discussion, new facilities compared to the paper material. But needs are still growing and new languages appear regularly, attempting to improve the structure and the interactivity of documents. Among these languages, some offer the possibility of animating and synchronizing media components. But the variety of these components (audio, video, text, image...) makes the animation a difficult problem. The author of a synchronized document provides a set of temporal constraints on the components 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 with piecewise convex costs, we studied different methods (linear programming, out-of-kilter, cost-scaling on the dual). However, these methods have been designed for graphs without any peculiar structure.

The graphs representing the temporal constraints are in fact very structured and very close to the class of graphs called series-parallel, and the methods designed for any graph appear to be sometimes inefficient. Hence we proposed a polynomial method, O(m³), more adapted to solve the problem on series-parallel graphs, and that we called aggregation.

But these graphs, although very close to the real cases, are still an idealization. We propose to measure the series-parallel aspect of a graph by defining the notion of almost series-parallel graph, based on the decomposition of the graph into series-parallel components. We discuss then about two problems: first how to identify the best decomposition of any graph into series-parallel components, and then how to profit of this decomposition and the efficiency of the aggregation method to find efficiently an optimal tension of the original graph. We call this approach reconstruction, because it consists in reconstructing progressively the original graph from a decomposition into series-parallel components, maintaining at each step of the reconstruction a minimal tension.