Let's start by citing a few problem statements that are more suited to graph databases.

Routing is a graph problem and much research has been done in that respect. One of the leading delivery services in the world uses a Neo4j-based solution to route packages in real time based on information being collected worldwide.

Social networks are problems suited for graphs since they leverage the connections of users to fetch data and decide on what is accessible and what isn't. Facebook, in particular, uses its graph search and has exposed it to the users to enable them to make better searches. Facebook relies heavily on the graph of people and their friends to curate the feed.

Recommendation is again a graph problem that can be solved using graph databases. While companies such as eBay originally relied on MySQL, they eventually turned to Neo4j.

While routing, social networks and recommendations are all obvious graph problems, companies have solved a host of problems by fitting the data into graphs in the recent past.

Search, for example, doesn't come across as a graph problem and is not a very intuitive one. However, Google uses its Knowledge Graph to give you search results based on how well connected a piece of content is to the term being searched. More recently, Facebook has leveraged its social graph to help search become better.

Medical research is another domain where graphs are being used. Medical data is highly interconnected and hence can benefit greatly from the use of graph databases. Companies are now using graph databases for drug discovery and storing medical information.

Storage of ontologies is increasingly being solved using graph databases, which are rapidly finding applications in machine learning and analytics. Companies are also using graph databases in domains such as energy supply and transportation.