Is this an interval graph?

Question

Background

An interval graph (Wikipedia, MathWorld, GraphClasses) is an undirected graph derived from a set of intervals on a line. Each vertex represents an interval, and an edge is present between two vertices if the corresponding intervals overlap. The following is an example interval graph with corresponding intervals.

Multiple linear-time algorithms exist that can determine whether a given graph is an interval graph or not. Many other graph-theoretical problems are also solvable in linear time for these graphs. Refer to the Wikipedia and GraphClasses links for details.

Note that you don't need to meet linear time complexity in this challenge.

Challenge

Given an undirected, connected, loop-free, nonempty graph as input, determine if it is an interval graph. ("loop-free" means that the graph does not contain any edge that goes from a vertex to itself.)

A graph can be taken as input using any standardized structures for an undirected graph, which include

• an adjacency matrix / adjacency list / incidence matrix, and
• an edge list (a list of (vi, vj) pairs).

If you use adjacency list or edge list, you may assume that the vertices are numbered consecutively (0- or 1-based). For all input methods, you can optionally take the number of vertices as the second input.

For output, you can choose to

• output truthy/falsy using your language's convention (swapping is allowed), or
• use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

The test cases are given as edge lists with 1-based vertex numbering.

Truthy

[(1,2)]
[(1,2), (1,3), (2,3)]
[(1,2), (1,3)]
[(1,2), (1,3), (2,3), (3,4), (4,5), (4,6), (5,6)]
[(1,2), (1,3), (2,3), (2,4), (3,4)]
[(1,2), (1,3), (1,4), (1,5), (1,6), (2,3), (3,4), (4,5), (5,6)]

Falsy

// contains a 4-cycle without chord
[(1,2), (1,3), (2,4), (3,4)]
[(1,2), (1,3), (2,3), (2,4), (3,5), (4,5)]

// contains an asteroidal triple (1, 4, 6)
[(1,2), (1,3), (2,3), (2,4), (2,5), (3,5), (3,6), (4,5), (5,6)]

Answer 1

Sage, 17 bytes

Graph.is_interval

Try it on Sage Cell; documentation

Answer 2

Jelly, 20 17 bytes

Œ!⁹ịⱮ;ⱮrḊɗ/€ẎḟƊ€Ạ

Try it online!

A dyadic link which takes the number of vertices as the left argument and the adjacency list as the right argument and returns 0 for an interval graph and 1 for not. This tests every possible ordering of vertices.

Uses the fact that iff the graph is an interval graph, there exists an ordering of vertices where if \$v_i\$ and \$v_k\$ are adjacent then all \$v_j\$ where \$i<j<k\$ must also be adjacent to \$v_i\$, as per the Mathworld article.

Full explanation to follow.

---

Original solution that assumes vertices are appropriately ordered

Jelly, 9 bytes

;ⱮrḊɗ/€Ẏḟ

Try it online!

A monadic link taking an ordered adjacency list as its argument and returning an empty list (falsy) if the argument represents an interval graph and a non-empty list (truthy) if not.

Explanation

    ɗ/€   | For each edge do the following as a dyad with the first vertex as the left argument and the second as the right:
;Ɱ        | - Concatenate the first edge to each of:
  r       |   - The range of integers from first vertex to second vertex inclusive
   Ḋ      | - Remove the first item (which will be [first vertex, first vertex])
       Ẏ  | Join outer lists together
        ḟ | Remove all edges found in the original list