Towards a study of low-complexity graphs