Here’s a really old FAQ that has a section on the GLU tessellator routines. Search for “concave” in here: LINK.
As for the concave polygon rasterization algorithm GClements mentioned, here’s a short write-up on that: Drawing Filled, Concave Polygons Using the Stencil Buffer. Yes , do keep in mind with modern OpenGL you don’t need multiple stencil passes for this anymore.