The LBFS Structure and Recognition of Interval Graphs

DOI10.1137/S0895480100373455zbMath1207.05131OpenAlexW1998389851MaRDI QIDQ3058537

Stephan Olariu, Lorna K. Stewart, Derek Gordon Corneil

Publication date: 3 December 2010

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480100373455

zbMATH Keywords

algorithmrecognitionchordal graphsAT-free graphsinterval graphsstructurelexicographic breadth first search

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (44)

Recognizing graph search trees ⋮ Computing the clique-separator graph for an interval graph in linear time ⋮ Happy set problem on subclasses of co-comparability graphs ⋮ The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs ⋮ A new LBFS-based algorithm for cocomparability graph recognition ⋮ Graph searches and their end vertices ⋮ Robinsonian matrices: recognition challenges ⋮ Homothetic polygons and beyond: maximal cliques in intersection graphs ⋮ Extending partial representations of interval graphs ⋮ Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number ⋮ Recognizing simple-triangle graphs by restricted 2-chain subgraph cover ⋮ Chronological rectangle digraphs which are two-terminal series-parallel ⋮ Recognition and characterization of chronological interval digraphs ⋮ Linearizing partial search orders ⋮ Interval scheduling and colorful independent sets ⋮ Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition ⋮ Recognizing interval bigraphs by forbidden patterns ⋮ A tie-break model for graph search ⋮ Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms ⋮ A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unit and single point interval graphs ⋮ A new graph parameter to measure linearity ⋮ Min-Orderable Digraphs ⋮ Interval graph representation with given interval and intersection lengths ⋮ Minimal obstructions for partial representations of interval graphs ⋮ Strict chordal and strict split digraphs ⋮ Non-edge orientation and vertex ordering characterizations of some classes of bigraphs ⋮ Extending partial representations of proper and unit interval graphs ⋮ End-vertices of LBFS of (AT-free) bigraphs ⋮ Star Partitions of Perfect Graphs ⋮ Happy set problem on subclasses of co-comparability graphs ⋮ Intersection graphs of non-crossing paths ⋮ Recognition and drawing of stick graphs ⋮ On the Power of Graph Searching for Cocomparability Graphs ⋮ On rectangle intersection graphs with stab number at most two ⋮ On the stab number of rectangle intersection graphs ⋮ The Recognition Problem of Graph Search Trees ⋮ Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review ⋮ Graph Classes and Forbidden Patterns on Three Vertices ⋮ Uniquely Restricted Matchings in Interval Graphs ⋮ A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs ⋮ Extending partial representations of subclasses of chordal graphs

This page was built for publication: The LBFS Structure and Recognition of Interval Graphs