  $\beta$-skeletons, a prominent member of the neighborhood graph family, have
interesting geometric properties and various applications ranging from
geographic networks to archeology. This paper focuses on developing a new, more
general than the present one, definition of $\beta$-skeletons based only on the
distance criterion. It allows us to consider them in many different cases, e.g.
for weighted graphs or objects other than points. Two types of
$\beta$-skeletons are especially well-known: the Gabriel Graph (for $\beta =
1$) and the Relative Neighborhood Graph (for $\beta = 2$). The new definition
retains relations between those graphs and the other well-known ones (minimum
spanning tree and Delaunay triangulation). We also show several new algorithms
finding $\beta$-skeletons.
