  The reassembling of a simple connected graph G = (V,E) is an abstraction of a
problem arising in earlier studies of network analysis. Its simplest
formulation is in two steps: (1) We cut every edge of G into two halves, thus
obtaining a collection of n=|V| one-vertex components. (2) We splice the two
halves of every edge together, not of all the edges at once, but in some
ordering \Theta of the edges that minimizes two measures that depend on the
edge-boundary degrees of assembled components.
  The edge-boundary degree of a component A (subset of V) is the number of
edges in G with one endpoint in A and one endpoint in V-A. We call the maximum
edge-boundary degree encountered during the reassembling process the
alpha-measure of the reassembling, and the sum of all edge-boundary degrees is
its beta-measure. The alpha-optimization (resp. beta-optimization) of the
reassembling of G is to determine an order \Theta for splicing the edges that
minimizes its alpha-measure (resp. beta-measure).
  There are different forms of reassembling. We consider only cases satisfying
the condition that if the an edge between disjoint components A and B is
spliced, then all the edges between A and B are spliced at the same time. In
this report, we examine the particular case of linear reassembling, which
requires that the next edge to be spliced must be adjacent to an already
spliced edge. We delay other forms of reassembling to follow-up reports.
  We prove that alpha-optimization of linear reassembling and minimum-cutwidth
linear arrangment (CutWidth) are polynomially reducible to each other, and that
beta-optimization of linear reassembling and minimum-cost linear arrangement
(MinArr) are polynomially reducible to each other.
