Consider a planar subdivision, with F faces, V vertices, E edges, and I face-vertex incidences. For simplicity, assume a non-degenerate situation in which each vertex occurs on the boundary cycle of each face only once. Then I is the sum over all faces of the number of vertices per face, or equivalently, the sum over all vertices of the number of incident faces. We have I = 2E, and therefore Euler's formula gives us:F + V = I/2 + 2.All I actually care about is:F + V < I/2.Does this also hold in for three-dimensional subdivisions, when F is the number of three-dimensional cells of the subdivision, and V and I are as defined above? Note that I am looking for an inequality that is independent of the number of one- and two-dimensional faces in the subdivision. When the cells are convex I can get something using quite a bit of geometry, but it seems to me that the requirement that the cells be convex is an artifact of my proof technique, and something more general should be possible and/or known. Does anybody have an idea where to look for the answer?
Relation between vertices, cells, and vertex-cell-incidences in 3D subdivisions
graph theory;cg.comp geom;topology