  The graph parameters highway dimension and skeleton dimension were introduced
to capture the properties of transportation networks. As many important
optimization problems like Travelling Salesperson, Steiner Tree or $k$-Center
arise in such networks, it is worthwhile to study them on graphs of bounded
highway or skeleton dimension.
  We investigate the relationships between mentioned parameters and how they
are related to other important graph parameters that have been applied
successfully to various optimization problems. We show that the skeleton
dimension is incomparable to any of the parameters distance to linear forest,
bandwidth, treewidth and highway dimension and hence, it is worthwhile to study
mentioned problems also on graphs of bounded skeleton dimension. Moreover, we
prove that the skeleton dimension is upper bounded by the max leaf number and
that for any graph on at least three vertices there are edge weights such that
both parameters are equal.
  Then we show that computing the highway dimension according to most recent
definition is NP-hard, which answers an open question stated by Feldmann et al.
Finally we prove that on graphs $G=(V,E)$ of skeleton dimension
$\mathcal{O}(\log^2 \vert V \vert)$ it is NP-hard to approximate the $k$-Center
problem within a factor less than $2$.
