Vertex splitting and the recognition of trapezoid graphs
From MaRDI portal
Publication:2275914
DOI10.1016/j.dam.2011.03.023zbMath1223.05301OpenAlexW2127787106MaRDI QIDQ2275914
George B. Mertzios, Derek Gordon Corneil
Publication date: 10 August 2011
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: http://dro.dur.ac.uk/9048/1/9048.pdf
Graph polynomials (05C31) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (8)
A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs ⋮ Recognizing simple-triangle graphs by restricted 2-chain subgraph cover ⋮ A recognition algorithm for simple-triangle graphs ⋮ The recognition of triangle graphs ⋮ An intersection model for multitolerance graphs: efficient algorithms and hierarchy ⋮ A characterization of interval orders with semiorder dimension two ⋮ A vertex ordering characterization of simple-triangle graphs ⋮ Succinct navigational oracles for families of intersection graphs on a circle
Cites Work
- Unnamed Item
- Matrix multiplication via arithmetic progressions
- Modular decomposition and transitive orientation
- Efficient graph representations
- Algorithmic graph theory and perfect graphs
- Proper and unit tolerance graphs
- On the structure of trapezoid graphs
- The recognition of tolerance and bounded tolerance graphs.
- On the 2-Chain Subgraph Cover and Related Problems
This page was built for publication: Vertex splitting and the recognition of trapezoid graphs