  The edge-hyper-Wiener index of a connected graph $G$ is defined as $WW_e(G) =
\frac{1}{2}\sum_{\lbrace e,f\rbrace \subseteq E(G)}d(e,f) +
\frac{1}{2}\sum_{\lbrace e,f\rbrace \subseteq E(G)}d(e,f)^2$. We develop a
method for computing the edge-hyper-Wiener index of partial cubes, which
constitute a large class of graphs with a lot of applications. It is also shown
how the method can be applied to trees. Furthermore, an algorithm for computing
the edge-hyper-Wiener index of benzenoid systems is obtained. Finally, the
algorithm is used to correct already known closed formulas for the edge-Wiener
index and the edge-hyper-Wiener index of linear polyacenes.
