How to connect two vertices with curved edge
As Leander has commented, if you want a circular arc, you can use the Spin tool, (AltR) to spin a single radius around the 3D cursor. 

If you want a more arbitrary curve interpolating through control points, you can select and position those points on an existing boundary, and use the shipped add-on: Loop Tools > 'Curve' to form it.