The answers will depend on the purpose of the scene-graph. If it exists "to represent a scene", then it's probably too generic / got too many responsibilities at the moment.
I'm designing a scenegraph and got some questions.
If the point of the graph is to express connections form one object to another (e.g. a character holding a gun), then it makes no sense for the items on the table to ever be a child of the table, unless someone has glued them on there.
If I have some items on a table the items would be childs of the table and the table would be a child of a room, but what happens if the item falls off the table for some reason. Do you automaticaly check the bounding volumes to remove the item from the table and then add it as a child to the room?
If the point of the graph is to accelerate frustum culling queries by grouping objects together, then you might have a reason to dynamically change the parent-child relationships like this -- but now the graph should no longer be used for expressing connections (such as the character holding a gun, or the mug glued to the table).
Trying to make one uber-graph that solves multiple problems at once (e.g. movement constraints/connections and efficient culling) will only result in a bloated data structure that does a bad job of all of these problems. Figure out what the point of your data structure is, and then make it do a good job of solving that problem as simply as possible.
To quote TomF:
It's a great theory, but sadly it's completely wrong. The world is not a big tree - a coffee mug on a desk is not a child of the desk, or a sibling of any other mug, or a child of the house it's in or the parent of the coffee it contains or anything - it's just a mug. It sits there, bolted to nothing. Putting the entire world into a big tree is not an obvious thing to do as far as the real world is concerned.
When dealing with connected objects, the 'real' data is generally the local transforms, with the world transforms being generated (so there's no need to save them, and they shouldn't be modified directly).
I have a local and world transform for each of the nodes in the graph. Is it normal to always work with the local transforms and then calculate the world transforms?
If you're grouping objects for the purposes of accelerating culling, then you don't need each object to have a relative transform from it's parent group -- that's unnecessary information for the problem at hand.
Also keep in mind that any physics engine is going to implement it's own "scene graph" internally, separate from your own, which is a good thing.
Adding the physics to the scene graph at the same time might be jumping the gun a little, I would suggest getting your head around it in terms of rendering, then deciding how or whether you can use the structure to help with physics.