This thesis is concerned with the problem of designing efficient parallel algorithms for various graph-theoretic problems. Our larger goal is to identify "tools" that would be useful in designing parallel algorithms for various graph-theoretic problems. We show that the concept of bridges plays a crucial role in the design of algorithms for the kinds of problems we consider. The specific problems we consider are the following. We give an $NC$ algorithm for finding vertex-disjoint $s_{1}, t_{1}$ and $s_{2}, t_{2}$ paths in an undirected graph. An important step in solving the general problem is solving the planar case. A new structural property yields the parallelization, as well as a simpler linear time sequential algorithm for this case. We extend the algorithm to the non-planar case by giving an $NC$ algorithm for finding a Kuratowski homeomorph, and, in particular, a homeomorph of $K_{3,3,}$ in a non-planar graph. We also present an efficient parallel algorithm for testing whether a graph is $k$ vertex-connected. To develop our algorithm we design an efficient parallel algorithm for the following disjoint $s-t$ paths problem: Given a graph and two specified vertices $s$ and $t$, find $k$ vertex-disjoint paths between $s$ and $t$, if they exist. If no such paths exist, find a set of at most $k$ - 1 vertices whose removal disconnects $s$ and $t$. We show how to modify the algorithm to find $k$ edge-disjoint paths, if they exist. This yields an efficient parallel algorithm for testing whether a graph is $k$ edge-connected. Finally, we describe more applications of the disjoint $s-t$ paths algorithm. This algorithm is also used as a subroutine in the algorithm for the two paths problem mentioned earlier.