ABSTRACT
Median graphs have been introduced as generalizations of trees and are used, for example, as median networks in genetics. (See Chapter 12.5.) As they are partial cubes and include all trees and hypercubes, which can be recognized in linear time, one might expect their recognition complexity to be somewhere between that of trees and partial cubes. This is indeed the case.
