When the model is given as an MSC, model checking can be done by constructing a suitable automaton for the linearizations of the partial order specified by the MSC, and the problem is coNP-complete. When the model is given by an MSC-graph, we consider two possible semantics depending on the synchronous or asynchronous interpretation of concatenating two MSCs. For synchronous model checking of MSC-graphs and HMSCs, we present algorithms whose time complexity is proportional to the product of the size of the description and the cost of processing MSCs at individual vertices. Under the asynchronous interpretation, we prove undecidability of the model checking problem. We, then, identify a natural requirement of boundedness, give algorithms to check boundedness, and establish asynchronous model checking to be Pspace-complete for bounded MSC-graphs and Expspace-complete for bounded HMSCs.