Do we need to trigger a re-render of the catlinks div? Can we?
It depends on what we get back from the server.
If we get back something that is compatible with what api.php?action=parse gives (prop.categorieshtml, from Skin::getCategories), which is what live preview in core uses as well, then we can just update it by replacing the old with the new html.
Note that the categories on the page are not refreshed even after multiple VE sessions. i.e. VE add category -> save -> VE add category -> save : results in a page that _displays_ only the categories at the beginning of the process.
Categories added via templates are also not displayed.