Medical image segmentation is crucial in various clinical applications, such as surgical planning and disease monitoring. However, existing learning approaches often struggle with accurately capturing the complex structures and spatial relationships in medical images. While graph neural networks (GNNs) offer a versatile approach by modeling element relationships, these methods face challenges in effectively learning intricate graph structures and relationships for medical image segmentation. To this end, we introduce MedGraph-RPE, which enhances Vision Graph UNet (ViG-UNet) with our novel Relative Positioning Encoding (RPE) module. During graph construction, RPE integrates relative positional relationships between nodes, improving learning capabilities without increasing model complexity. This module provides explicit spatial relationship information, enabling more precise segmentation of complex structures. MedGraph-RPE also preserves contextual information, ensuring that crucial spatial data is retained throughout the learning process. Empirically, our comprehensive experiments demonstrate state-of-the-art performance in brain tumor and skin lesion segmentation tasks.