Medical image segmentation is very essential for computer-aided diagnosis in the field of medical imaging. In the last decade, Deep Learning-based frameworks (e.g., UNet) have been widely used in medical applications such as image segmentation tasks. Recently, numerous Transformer-based frameworks are presented for the image segmentation tasks as their design can utilize long-range dependencies. Transformer's design has a weak inductive bias since it does not take advantage of local relationships between pixels and lacks scale invariance. Consequently, Transformers require large datasets for convergence whereas the availability of massive medical datasets is challenging. In this paper, we present a graph-based approach replacing Transformer design to capture long-range dependencies and reduce computational cost. Our proposed framework achieves competitive performance using publicly available dataset Synapse.