강정규 그래프
모든 정점이 동일한 수의 이웃을 갖고, 인접 여부에 따라 공통 이웃 수가 일정한 특수 그래프다. 대칭성이 매우 높아 일반적인 알고리즘으로 구분하기 매우 까다로운 구조다.
3-WL도 못 푸는 그래프 난제를 선형 시간에 해결하는 DRESS 알고리즘