Rapid progress in graphene-based applications is calling for new processing techniques for creating graphene components with different shapes, sizes, and edge structures. Here we report a controlled cutting process for graphene sheets, using nickel nanoparticles as a knife that cuts with nanoscale precision. The cutting proceeds via catalytic hydrogenation of the graphene lattice, and can generate graphene pieces with specific zigzag or armchair edges. The size of the nanoparticle dictates the edge structure that is produced during the cutting. The cutting occurs along straight lines and along symmetry lines, defined by angles of 60 degrees or 120 degrees, and is deflected at free edges or defects, allowing practical control of graphene nano-engineering.