Skip to main content

Research Repository

Advanced Search

Vertex Splitting and the Recognition of Trapezoid Graphs

Mertzios, G.B.; Corneil, D.G.

Vertex Splitting and the Recognition of Trapezoid Graphs Thumbnail


Authors

D.G. Corneil



Abstract

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.

Citation

Mertzios, G., & Corneil, D. (2011). Vertex Splitting and the Recognition of Trapezoid Graphs. Discrete Applied Mathematics, 159(11), 1131-1147. https://doi.org/10.1016/j.dam.2011.03.023

Journal Article Type Article
Publication Date Jul 6, 2011
Deposit Date Dec 8, 2011
Publicly Available Date Mar 28, 2024
Journal Discrete Applied Mathematics
Print ISSN 0166-218X
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 159
Issue 11
Pages 1131-1147
DOI https://doi.org/10.1016/j.dam.2011.03.023
Keywords Trapezoid graphs, Permutation graphs, Recognition, Vertex splitting, Polynomial algorithm.

Files

Accepted Journal Article (424 Kb)
PDF

Copyright 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.





You might also like



Downloadable Citations