I am currently working on a 2D finite element code with a mesh that contains duplicate nodes at certain interfaces where jumps occur. In order to set up the appropriate linear systems, I have to take the mesh connectivity information and locations of mesh nodes, and manipulate them to determine which elements are adjacent across an interface.
To get an idea of potential run-time scaling in serial, I've expressed all of the asymptotic complexities of each algorithm in terms of the number of nodes (or the number of degrees of freedom), because that is a natural complexity metric. I'm able to do that using well-known facts about planar graphs.
I'd like to be able to extend these algorithms to 3D meshes, and I'd like to have an idea of their complexity in terms of the number of nodes. I'm also sure that 3D meshes are not necessarily planar graphs. Is there a result that bounds the number of edges, facets, and elements of a 3D mesh in terms of the number of mesh nodes? Assuming a simplicial mesh is fine; results for hexahedral meshes would also be interesting, too.
I'm sure that none of what I'm doing is new; I just don't work with meshes very much, so I have no idea where to look for the result.