  Graph theory is a promising approach in handling the problem of estimating
the connectivity probability of vehicular ad-hoc networks (VANETs). With a
communication network represented as graph, graph connectivity indicators
become valid for connectivity analysis of communication networks as well. In
this article, we discuss two different graph-based methods for VANETs
connectivity analysis showing that they capture the same behavior as estimated
using probabilistic models. The study is, then, extended to include the case of
directed VANETs, resulting from the utilization of different communication
ranges by different vehicles. Overall, the graph-based methods prove a robust
performance, as they can be simply diversified into scenarios that are too
complex to acquire a rigid probabilistic model for them.
