Postgresql - get relation name from relid or RelOptInfo data structure
You want RelationGetRelationName(Relation).

If you don't have a Relation, use get_rel_name(Oid). This uses the syscache so you must have an open transaction. Beware though, it doesn't schema-qualify the name. If you need that, you should probably do a syscache lookup yourself (see the code for get_rel_name in src/backend/utils/cache/lsyscache.c) so you can also get_namespace_name the schema name. Then use quote_qualified_identifier.

I am constantly surprised that Pg doesn't seem to have a public C-level equivalent of the regclass formatting in regclassout. See src/backend/utils/adt/regproc.c.

There's generate_qualified_relation_name, but it's static for some reason. I think I'll submit a patch proposing to move it, generate_relation_name  and get_relation_name to lsyscache.c and make them public.

In the mean time I suggest shameless ripping off what generate_relation_name or generate_qualified_relation_name does if you're doing something where get_rel_name isn't good enough.

Update: patch submitted. Feel free to shamelessly rip off that function.