We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Vertex splitting and the recognition of trapezoid graphs.

Mertzios, G.B. and Corneil, D.G. (2011) 'Vertex splitting and the recognition of trapezoid graphs.', Discrete applied mathematics., 159 (11). pp. 1131-1147.


Trapezoid graphs are the intersection family of trapezoids where every trapezoid has a pair of opposite sides lying on two parallel lines. These graphs have received considerable attention and lie strictly between permutation graphs (where the trapezoids are lines) and cocomparability graphs (the complement has a transitive orientation). The operation of “vertex splitting”, introduced in (Cheah and Corneil, 1996), first augments a given graph G and then transforms the augmented graph by replacing each of the original graph’s vertices by a pair of new vertices. This “splitted graph” is a permutation graph with special properties if and only if G is a trapezoid graph. Recently vertex splitting has been used to show that the recognition problems for both tolerance and bounded tolerance graphs is NP-complete (Mertzios et al., 2010). Unfortunately, the vertex splitting trapezoid graph recognition algorithm presented in (Cheah and Corneil, 1996) is not correct. In this paper, we present a new way of augmenting the given graph and using vertex splitting such that the resulting algorithm is simpler and faster than the one reported in (Cheah and Corneil, 1996) F. Cheah and D.G. Corneil, On the structure of trapezoid graphs. Discrete Applied Mathematics, 66 2 (1996), pp. 109–133.

Item Type:Article
Keywords:Trapezoid graphs, Permutation graphs, Recognition, Vertex splitting, Polynomial algorithm.
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:NOTICE: this is the author’s version of a work that was accepted for publication in Discrete Applied Mathematics. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Discrete Applied Mathematics, 159, 11, 2011, 10.1016/j.dam.2011.03.023.
Date accepted:No date available
Date deposited:16 September 2014
Date of first online publication:July 2011
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar