In this study, we present a novel graph-based methodology for an accurate classification of cardiac arrhythmia diseases using a single-lead electrocardiogram (ECG). The proposed approach employs the visibility graph technique to generate graphs from time signals. Subsequently, informative features are extracted from each graph and then fed into classifiers to match the input ECG signal with the appropriate target arrhythmia class. The six target classes in this study are normal (N), left bundle branch block (LBBB), right bundle branch block (RBBB), premature ventricular contraction (PVC), atrial premature contraction (A), and fusion (F) beats. Three classification models were explored, including graph convolutional neural network (GCN), multi-layer perceptron (MLP), and random forest (RF). ECG recordings from the MIT-BIH arrhythmia database were utilized to train and evaluate these classifiers. The results indicate that the multi-layer perceptron model attains the highest performance, showcasing an average accuracy of 99.02%. Following closely, the random forest achieves a strong performance as well, with an accuracy of 98.94% while providing critical intuitions.