For the first problem a complete characterization of the path layout construction problem for networks with hop count bounded by $h$ and load bounded by $l$ is presented. We prove that the problem of determining the existence of such layouts is NP-complete for every given values of $h$ and $l$ (any given stretch factor), except for the cases $h=2, l=1$ and $h=1$, any $l$, for which we give polynomial-time layout constructions (for the case of an unbounded stretch factor).
For both problems a geometric approach is presented, that enables a simple argumentation about optimality of layout constructions, for chain, augmented path and ring networks. Stated in graph-theoretic terms, the problem amounts to the embedding of the vertices of a graph with $N$ nodes onto the points $1,2,\cdots,N$ of the $x$-axis. We look for a graph with minimum diameter $D_c(N)$, for which such an embedding is possible, given a bound $c$ on the cutwidth of the embedding. We develop a technique to embed the nodes of such graphs into the integral lattice points in the $c$-dimensional $l_1$-sphere. Using geometric arguments, we derive analytical bounds for $D_c(N)$, which result in substantial improvements on some known lower and upper bounds. This geometric approach helps also in understanding the duality between the parameters of hop count and load in certain layout constructions.