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.
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
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.
The test cases are given as edge lists with 1-based vertex numbering.
[(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)]
// 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)]