The algorithmic decidability of elementary theories of certain classes of graphs, such as homogeneous, planar, bipartite planar, and critical nonplanar, is discussed. For the first three classes we prove the undecidability of elementary theories, and for the last, decidability with a supplementary predicate. We also prove the undecidability of theory of Abelian loops by an interpretation in it of theory of bipartite homogeneous 3rd degree graphs.