The availability of the large amount of Automatic Identification System (AIS) data has fostered many studies on maritime vessel traffic during the recent years, often representing vessels and ports relationships as graphs. Although the continuous research effort, only a few works explicitly study the evolution of such graphs and often consider coarse-grained time intervals. In this context, our ultimate goal is to fill this gap by providing a system- atic study in the graph evolution by considering voyages over time. a three years of AIS data from the coastal waters of United States. By mining the arrivals and departures of vessels from ports, we build a graph consisting of vessel voyages between ports. We then provide a study on topological features calculated from such graphs with a strong focus on their temporal evolution. Finally, we discuss the main limitations of our approach and the future perspectives that will spawn from this work.