Depth-contours are an essential part of any hydrographic chart—a map of a waterbody intended for safe ship navigation. Traditionally these were manually drawn by skilled hydrographers from a limited set of surveyed depth measurements. Nowadays this process of map making is shifted towards the digital domain, not in the last place because of the huge amounts of data resulting from modern surveying techniques. Furthermore, the task of automating the process of cartographic generalization that depends on subjective criteria is challenging. The produced depth-contours should comply with the four hydrographic generalization constraints of safety, legibility (smoothness), topology and waterbody morphology. I show that grid-based approaches to generalize depth contours that are currently used in practice do not always comply with those fundamental generalization constraints. Most notably, the safety constraint, that ensures that a map never indicates an area as being shallower than measured, is often violated. But also the legibility and morphology constraints are not always optimally respected. Furthermore, heterogeneous datasets (that contain a transition of very sparse to very dense data), can lead to unwished interpolation artifacts, when the popular Inverse Distance Weighting (IDW) spatial interpolation method is used. Part of this problem is the non-adaptive nature of IDW, that requires the user to re-set the interpolation parameters when the spatial distribution of the input point changes. I present and prototype a novel surface-based approach for the generalization of hydrographic depth-contours that is based on the Voronoi Diagram (VD) and performs generalization on the surface that defines the contours, rather on the contour lines individually. Through the VD, a fully adaptive, automatic and smooth spatial interpolation method known as the Laplace interpolant is coupled with a Delaunay Triangulation (DT) data structure that contains all data points with their exact planimetric coordinates. Using this concept a number of operators is defined that are able to perform the relevant cartographic generalization operations for hydrographic contours: simplification, smoothing, aggregation, omission and enlargement. The significance of the proposed approach lies herein that it honors all four hydrographic generalization constraints, most notably: it is guaranteed to be safe. As opposed to current automated approaches, it does therefore not require any form of manual safety verification. And, because all of the employed algorithms are local, it is also well scalable to big datasets in principle.