  In this paper we study a generalization of the classic \emph{network creation
game} in the scenario in which the $n$ players sit on a given arbitrary
\emph{host graph}, which constrains the set of edges a player can activate at a
cost of $\alpha \geq 0$ each. This finds its motivations in the physical
limitations one can have in constructing links in practice, and it has been
studied in the past only when the routing cost component of a player is given
by the sum of distances to all the other nodes. Here, we focus on another
popular routing cost, namely that which takes into account for each player its
\emph{maximum} distance to any other player. For this version of the game, we
first analyze some of its computational and dynamic aspects, and then we
address the problem of understanding the structure of associated pure Nash
equilibria. In this respect, we show that the corresponding price of anarchy
(PoA) is fairly bad, even for several basic classes of host graphs. More
precisely, we first exhibit a lower bound of $\Omega (\sqrt{ n / (1+\alpha)})$
for any $\alpha = o(n)$. Notice that this implies a counter-intuitive lower
bound of $\Omega(\sqrt{n})$ for very small values of $\alpha$ (i.e., edges can
be activated almost for free). Then, we show that when the host graph is
restricted to be either $k$-regular (for any constant $k \geq 3$), or a
2-dimensional grid, the PoA is still $\Omega(1+\min\{\alpha,
\frac{n}{\alpha}\})$, which is proven to be tight for
$\alpha=\Omega(\sqrt{n})$. On the positive side, if $\alpha \geq n$, we show
the PoA is $O(1)$. Finally, in the case in which the host graph is very sparse
(i.e., $|E(H)|=n-1+k$, with $k=O(1)$), we prove that the PoA is $O(1)$, for any
$\alpha$.
