Median graphs and triangle-free graphs

Let M(m, n) be the complexity of checking whether a graph G with m edges an d n vertices is a median graph. We show that the complexity of checking whe ther G is triangle-free is at most O(M(m, m)). Conversely, we prove that th e complexity of checking whether a given graph is a median graph is at most O(m log n + T(m log n, n)), where T(m, n) is the complexity of finding all triangles of the graph. We also demonstrate that, intuitively speaking, th ere are as many median graphs as there are triangle-free graphs. Finally, t hese results enable us to prove that the complexity of recognizing planar m edian graphs is linear.