Grafos ordenáveis por vizinhança gêmea são definidos como aqueles que admitem uma ordem de eliminação em que cada vértice a ser removido possui a propriedade de que todos os seus vizinhos são gêmeos verdadeiros. Essa classe de grafos foi introduzida recentemente, inspirada por semelhanças entre as ordens de eliminação de grafos cordais e dualmente cordais. Neste trabalho, abordamos o problema de reconhecimento para essa classe de grafos. Propomos um novo algoritmo que utiliza duas passadas de uma variante da Busca em Largura Lexicográfica (LBFS) para reconhecer grafos ordenáveis por vizinhança gêmea em tempo linear.