Extending Partial Representations of Trapezoid Graphs

摘要

A trapezoid graph is an intersection graph of trapezoids spanned between two horizontal lines. The partial representation extension problem for trapezoid graphs is a generalization of the recognition problem: given a graph G and an assignment ξ of trapezoids to some vertices of G, can ξ be extended to a trapezoid intersection model of the entire graph G? We show that this can be decided in polynomial time. Thus, we determine the complexity of partial representation extension for one of the two major remaining classes of geometric intersection graphs for which it has been unknown (circular-arc graphs being the other).