Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
Vertex Splitting and the Recognition of Trapezoid Graphs
Mertzios, G.B.; Corneil, D.G.
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.
Journal Article Type | Article |
---|---|
Publication Date | Jul 6, 2011 |
Deposit Date | Dec 8, 2011 |
Publicly Available Date | Sep 16, 2014 |
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. |
Public URL | https://durham-repository.worktribe.com/output/1502568 |
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
The complexity of growing a graph
(2022)
Presentation / Conference Contribution
Payment scheduling in the Interval Debt Model
(2023)
Presentation / Conference Contribution
The complexity of computing optimum labelings for temporal connectivity
(2022)
Presentation / Conference Contribution
The complexity of temporal vertex cover in small-degree graphs
(2022)
Presentation / Conference Contribution
The complexity of transitively orienting temporal graphs
(2021)
Presentation / Conference Contribution
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search