The most common way is by having 'holes' defined in the mesh (ie. maybe use 1 bit for each point to determine whether it exists or not) and then creating extra

The most common way is by having 'holes' defined in the mesh (ie. maybe use 1 bit for each point to determine whether it exists or not) and then creating extra geometry to attach to that. Alternatively, you can try a voxel-based approach and then use an algorithm like Marching-cubes to reconstruct a smooth mesh over the top of it. Or, you could change the heightmap data to also include X/Z displacement as well as Y displacement. This would allow some shallow caves and small overhangs, but nothing too crazy. There will be plenty of other methods you could use too, these are just a starting point.