d-trapezoid graphs

Definition:

Let L₁ ...L_d be d parallel lines in the plane. A d-trapezoid is the polygon obtained by choosing an interval I_i on every line L_i and connecting the left, resp. right endpoint of I_i with the left, resp. right endpoint of I_i+1 .
A graph is a d-trapezoid graph if it has an intersection model consisting of d-trapezoids between d parallel lines.

Input:	A graph G in this class.
Output:	True iff each vertex of G can be assigned one colour out of 3 such that whenever two vertices are adjacent, they have different colours.

Input:	A graph G in this class and an integer k.
Output:	True iff G contains a set S of pairwise adjacent vertices, with \|S\| >= k.

Input:	A graph G in this class and an integer k.
Output:	True iff the vertices of G can be partitioned into k sets S_i, such that whenever two vertices are in the same set S_i, they are adjacent.

Assuming an intersection model is given [1120] .

Whether the cliquewidth of the graphs in this class is bounded by a constant k .
The cliquewidth of a graph is the number of different labels that is needed to construct the graph using the following operations:

creation of a vertex with label i,
disjoint union,
renaming labels i to label j,
connecting all vertices with label i to all vertices with label j.

Input:	A graph G in this class.
Output:	An expression that constructs G according to the rules for cliquewidth, using only a constant number of labels. Undefined if this class has unbounded cliquewidth.

Input:	A graph G in this class and an integer k.
Output:	True iff each vertex of G can be assigned one colour out of k such that whenever two vertices are adjacent, they have different colours.

Input:	A graph G in this class and an integer k.
Output:	True iff the cutwidth of G is at most k (see bounded cutwidth).

Input:	A graph G in this class and an integer k.
Output:	True iff G contains a set S of vertices, with \|S\| <= k, such that every vertex in G is either in S or adjacent to a vertex in S.

Input:	A graph G in this class and an integer k.
Output:	True iff G contains a set S of vertices, with \|S\| <= k, such that every cycle in G contains a vertex from S.

Input:	A graph G in this class.
Output:	True iff G has a simple cycle that goes through every vertex of the graph.

Input:	A graph G in this class.
Output:	True iff G has a simple path that goes through every vertex of the graph.

Input:	A graph G in this class and an integer k.
Output:	True iff G contains a set S of pairwise non-adjacent vertices, such that \|S\| >= k.

Input:	A graph G.
Output:	True iff G is in this graph class.

Input:	A graph G in this class and an integer k.
Output:	True iff the treewidth of G is at most k (see bounded treewidth).

Assuming an intersection model is given [1417] .

Input:	A graph G in this class with weight function on the vertices and a real k.
Output:	True iff G contains a set S of pairwise adjacent vertices, such that the sum of the weights of the vertices in S is at least k.

Input:	A graph G in this class with weight function on the vertices and a real k.
Output:	True iff G contains a set S of vertices, such that the sum of the weights of the vertices in S is at most k and every cycle in G contains a vertex from S.

Input:	A graph G in this class with weight function on the vertices and a real k.
Output:	True iff G contains a set S of pairwise non-adjacent vertices, such that the sum of the weights of the vertices in S is at least k.

Assume an intersection model is given [1120] .

Graphclass: d-trapezoid

References

Equivalent classes

Complement classes

Inclusions

Map

Minimal superclasses

Maximal subclasses

Problems