Re: Yes but no but
"It is, however, pretty easy to encode them in relational databases (e.g. two tables, one of nodes, and one of edges). Directions are also easy to express."
That's great, but it's a complete anti-pattern. You've effectively created a write-only graph store.
Take a gander back at the article, for example.
"but writing a SQL statement that will find all my friends' friends that are two nodes away should always cause a program a severe migraine..."
Finding nodes 2 hops away isn't too complex a sql query, just two joins really. What about 3 hops? Well, we're suddenly into N+1 territory, and it's swiftly downhill from there. Heaven help you if you want to do something actually Graph-y and iterative like PageRank.
The point of a graph store isn't to store something an RDBMS can't. There isn't any such thing. Throw enough link tables and type tables and joins at a problem and you can model anything. The point is to support efficient, expressive querying of that data in a way an RDBMS will really, really struggle with. That's the point of NoSQL stores in general.
That's also why you find there are two distinct graph technologies. You've got those concerned with storing graphs and doing rapid retrieval of small subsets (like Neo, Titan etc.), and you've got those models concerned with doing bulk analysis of a whole graph, usually based on Pregel.
One area where graph systems are hammering RDBMS in enterprise land at the minute is MDM/DQ platforms. Dig under the hood of the latest offerings from any of the big boys there and you'll find their traditional RDBMS backends have been torn out for hipster graph backends. They're just better for that kind of any-entity-to-any-entity model, and that is often what we're dealing with in real life with real data.