Vertex splitting and the recognition of trapezoid graphs

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

zbMATH Keywords

polynomial algorithmrecognitiontrapezoid graphspermutation graphsvertex splitting

Mathematics Subject Classification ID

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