It is well known that any directed graph induces an undirected graph by forgetting the direction of the edges and keeping the underling structure. In fact, this assignment can be extended to consider graph morphisms, thus obtaining a functor from the category of simple directed graphs and directed graph morphism, to the category of undirected graphs and undirected graph morphisms. This particular functor is known as a “forgetful” functor, since it forgets the notion of direction.

In this talk, I will present a bijective functor that relates the category of simple directed graphs with a particular category of undirected graphs, whose objects we call “prime graphs”. Intuitively, prime graphs are undirected bipartite graphs endowed with a label that evokes a notion of direction. As an application, we use two undirected graph techniques to study directed graphs: spectral clustering and network alignment.