Let the coboxicity of a graph G be denoted by cob(G), and the threshold dimension by t(G). For fixed k≥3, determining if cob(G)≥k and t(G)•k are both NP-complete problems. The authors show that if G is a comparability graph, then they can determine if cob(G)•2 in polynomial time. This result shows that it is possible to determine if the interval dimension of a poset equals 2 in polynomial time. If the clique covering number of G is 2, the authors show that one can determine if t(G)•2 polynomial time. Sufficient conditions on G are given for cob(G)•2 and for t(G)•2.
