In classical differential geometry, a central question has been whether abstract surfaces with given geometric features can be realized as surfaces in Euclidean space. Inspired by the rich theory of embedded triply periodic minimal surfaces, we seek examples of triply periodic polyhedral surfaces that have an identifiable conformal structure. In particular we are interested in explicit cone metrics on compact Riemann surfaces that have a realization as the quotient of a triply periodic polyhedral surface. We use graph theory to develop construction methods on building triply periodic polyhedral surfaces. which enables us to expand Coxeter-Petrie's classification of infinite regular polyhedral surfaces. Results include examples that shed new light on existing minimal or algebraic surfaces, such as the Schwarz minimal P-, D-surfaces, Fermat's quartic, Schoen's minimal I-WP surface, and Bring's curve.