The study of the emerging structures of maritime networks should provide a better understanding of transportation patterns at spatial, temporal and semantic levels. This paper introduces a graph-based model for representing maritime trajectories combined with a spatial hexagonal indexing annotation. This model is implemented on top of a graph database and experimented with a sample of maritime historical data. A series of Cypher queries illustrate the potential of the approach for the extraction of some representative maritime network structures.