drupal views : display previous nodes
It would be best to create a page/block (basically just a different views display) to achieve that.

The constraints that you have i.e. Previous and Related can only find a practical application if your videos belong to the same category.

If I am getting the question right what you are better off doing is creating another block which displays all videos irrespective of the categories.