In this work, an attempt is made to characterize the variation in the complexity of the surface electromyography (sEMG) signals in fatigue. For this, sEMG signals from 58 healthy volunteers are recorded from the biceps brachii muscle under well-defined dynamic contraction protocol. The contractions are segmented, and the initial and final curls are extracted. These are considered as nonfatigue and fatigue respectively. Further, visibility graphs are constructed at multiple scales, and median degree centrality (MSMC) is calculated in them. To quantify the variations in the MSMC, two features namely, the average and standard deviation are calculated. The results reveal that the recorded signals are non-stationary. The constructed networks form distinct clusters in space. The MSMC feature shows a decreasing trend with scale in both nonfatigue and fatigue conditions. Additionally, the extracted features have higher values in fatigue. This may be due to the motor unit synchronization, which causes an increase in connectivity between nodes. All the extracted features showed statistical significance with p<0.005. This approach of analysis can be extended to characterize muscle in other neuromuscular conditions. © 2019 IEEE.