Planar-faced mesh surfaces, also known as polyhedral surfaces, that possess vertex-offsets are useful in architectural design for constructing supporting structures, and also of interest in discrete differential geometry. We consider the existence and computation of vertex-offset meshes of general polyhedral surfaces and, specifi- cally, study how the existence of vertex offsets is dictated by the face shape, mesh surface geometry and mesh surface topology. This extends the study in [Pottmann et al. 2007; Pottmann and Wallner 2008] on vertex-offset meshes of simply-connected circular quad meshes.