Efficient construction of B-essential graphs