Interval-Permutation Segment Graphs

2019/08/27 by Zlatko Joveski, Joveski, Zlatko, Jeremy Spinrad +2
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computer science #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph #Graph Labeling and Dimension Problems #Interval (graph theory) #Mathematics #Permutation (music) #Permutation graph #Physics #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.1908.10491

arxiv created 2019/08/27 · openalex publication_date 2019/08/27 · arxiv updated 2019/08/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this work, we introduce the interval permutation segment (IP-SEG) model that naturally generalizes the geometric intersection models of interval and permutation graphs. We study properties of two graph classes that arise from the IP-SEG model and present a family of forbidden subgraphs for these classes. In addition, we present polynomial algorithms for the clique and independent set problems on these classes, when the model is given as part of the input.

Citations

• Trapezoid graphs and their coloring
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On grid intersection graphs
• A vertex ordering characterization of simple-triangle graphs

Related

• k-Gap Interval Graphs
• Interval k-Graphs and Orders
• Identification, location–domination and metric dimension on interval and permutation graphs. I. Bounds
• Identification, Location-Domination and Metric Dimension on Interval and Permutation Graphs. II. Algorithms and Complexity
• Interval H-graphs : Recognition and forbidden obstructions