The paper presents a novel method for global motion planning of robotic systems that interact with the environment through contacts. The method formulates the motion-planning problem as a shortest-path problem in a Graph of Convex Sets (GCS), where each vertex represents a contact mode and edges represent valid transitions between modes. The quasi-static dynamics within each contact mode are modeled using semidefinite programming to relax the nonconvex bilinear constraints. This results in a tight convex relaxation of the overall planning problem, which can be efficiently solved and rounded to find a feasible contact-rich trajectory. The method is evaluated on the task of planar pushing, demonstrating that it generates plans with an average optimality gap of 10% and successfully finds trajectories where state-of-the-art baselines fail. The quality of these plans is validated on a real robotic system. The paper also reviews related work and provides a detailed background on shortest paths in GCS and semidefinite relaxation of quadratically constrained quadratic programs.The paper presents a novel method for global motion planning of robotic systems that interact with the environment through contacts. The method formulates the motion-planning problem as a shortest-path problem in a Graph of Convex Sets (GCS), where each vertex represents a contact mode and edges represent valid transitions between modes. The quasi-static dynamics within each contact mode are modeled using semidefinite programming to relax the nonconvex bilinear constraints. This results in a tight convex relaxation of the overall planning problem, which can be efficiently solved and rounded to find a feasible contact-rich trajectory. The method is evaluated on the task of planar pushing, demonstrating that it generates plans with an average optimality gap of 10% and successfully finds trajectories where state-of-the-art baselines fail. The quality of these plans is validated on a real robotic system. The paper also reviews related work and provides a detailed background on shortest paths in GCS and semidefinite relaxation of quadratically constrained quadratic programs.