The use of PC clusters interconnected by high performance local networks is one of the major current trends in parallel/distributed computing. We give coarse-grained, BSP-like, parallel algorithms to solve many problems arising in the context of interval graphs, namely connected components, maximum weighted clique, BFS and DFS trees, minimum interval covering, maximum independent set and minimum dominating set. All of the described p-processor parallel algorithms require only constant or O(log p) number of communication rounds and are efficient in practice, as demonstrated by our experimental results obtained on a Fast Ethernet based PC cluster.