What is the best type of Graph for a 4000 x 4000 plane? (if any)

General
1

I am guessing recast… but Im not totally sure would like some reassurance on this?

2

The size of the plane has no importance. The important thing is how detailed you want the navmesh on top of it to be. You can use a grid graph with a node size of 4 for example. However as you have noted yourself, recast is probably the best option (tends to be for large worlds).