Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 IntervalGraph

Source Notebook

Construct the intersection graph of intervals

Contributed by: Wolfram Staff (original content by Sriram V. Pemmaraju and Steven S. Skiena)

ResourceFunction["IntervalGraph"][{interval1,interval2,…}]

constructs the interval Graph defined by the intervali.

Details and Options

ResourceFunction["IntervalGraph"][{interval1,interval2,…}] returns an undirected Graph with a vertex for each intervali and edges between vertices whose intervals intersect.
The intervali must be defined on the real line.
ResourceFunction["IntervalGraph"] accepts the options of Graph.

Examples

Basic Examples (1) 

The interval Graph of three intervals, two of which are overlapping:

In[1]:=
ResourceFunction[ "IntervalGraph"][{Interval[{1, 4}], Interval[{2, 6}], Interval[{7, 8}]}, VertexLabels -> "Name"]
Out[1]=

Properties and Relations (2) 

Graphs returned by IntervalGraph are chordal and perfect:

In[2]:=
ResourceFunction[ "IntervalGraph"][{Interval[{1, 6}], Interval[{2, 4}], Interval[{3, 11}], Interval[{5, 10}], Interval[{7, 8}], Interval[{9, 13}], Interval[{12, 14}]}, VertexLabels -> "Name", GraphLayout -> "CircularEmbedding"]
Out[2]=
In[3]:=
ResourceFunction["PerfectGraphQ"][%]
Out[3]=

Star graphs can be constructed as interval graphs:

In[4]:=
n = 7;
In[5]:=
ResourceFunction["IntervalGraph"][ Append[Interval /@ Partition[Range[2 n], 2], Interval[{1, 2 n}]], GraphLayout -> "SpringEmbedding"]
Out[5]=
In[6]:=
StarGraph[n + 1]
Out[6]=

Version History

  • 1.0.0 – 22 July 2020

License Information