For my 4X game, I'm considering switching over from a grid-based system to a star-to-star movement (basically a node-based system where every node is connected to another node), similar to Master of Orion 1/2. One aspect of this is that I will introduce "Supply Range" which restricts where your ships can go. Each owned system have its own supply range. So the problem is now broken down to this:

Each node has a circle with radius of s (supply range)
When moving from a node to another, the line between the two nodes must be fully contained by circles. (X1,Y1 is starting position, X2, Y2 is destination)
If the line is not fully contained, the route is invalid.

Here's two examples:
Two star systems on the opposite sides of galaxy are owned by the player, but no stars in middle are owned, so the player can't send his ships directly from one node to another.
One fleet is moving from one star system to an unexplored star system that is within range, so the route is valid.

I tried looking this up, but was unable to find any resources. Maybe I'm looking with wrong search terms.

I think I do have an idea of how to do this:

Find intersection points along the line where it intersects with circles, and call them l1, l2, l3,...
For each lx, lx+1, check to see if both points is within any circle, if so, remove from list.
If list is empty after processing, then the line is fully contained.
If list have at least one segment remaining, then the line is not fully contained.

Is this a good approach to this problem? Any pitfalls I missed?

There is a serious flaw in your scheme: not all routes are straight lines, as you might be forced to make deviations to remain inside the supplied region (a longer path is better than no path at all).
Your problem is equivalent to pathfinding through caverns consisting of the union of hollow balls (i.e. node supply ranges) dug into solid rock (i.e. unsupplied space): straight lines might go through rock, but maybe you can detour around corners.

If you don't want to maintain a traditional pathfinding graph, you can presumably build it on the fly: from each ball, you can only go to intersecting balls, which are easy to find with suitable spatial indexing. Then you only need to sort "portals" by angle to see whether you need to make a turn at either corner of the intersection of two balls, or you can go straight.

Alternatively one could build the navigation graph from circle intersection points and stars. That should give the absolute shortest path.

After reading your responses, I realized that if the star was just a bit off the beaten path, but is within supply range, it'd be annoying for the player to have to send the fleet to an adjacent star then issuing another order to finally arrive at the destination. In Master of Orion 1/2, it just checks whether or not the destination is within range, not if the route itself has left the range.

Alternatively one could build the navigation graph from circle intersection points and stars. That should give the absolute shortest path.

This looks promising, since I plan on adding obstacles such as black holes or nebulaes that you need to navigate around. Are there tutorials on creating a navigation graph? I remember trying to find some, but was unable to do so.