Online Help

IntervalGraph(c) returns an interval graph for the collection of intervals C.

Each element of the input C must be a range or a RealRange expression. A range a..b is interpreted as the closed real interval from a to b. To specify open or half-open intervals, you can use RealRange.

The vertices of the resulting graph correspond to the intervals given in C. An edge between vertices exists if the corresponding intervals have non-empty intersection.

IsIntervalGraph(G) tests whether the graph G could be expressed as an interval graph for some collection of intervals.

An interval graph is the intersection graph of a set of intervals on the real line. For any vertices $i$, $j$ in the graph, an edge between $i$ and $j$ exists if and only if the intervals $i$ and $j$ have non-empty intersection.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$G≔\mathrm{IntervalGraph}\left(\left[1..3\,2..4\,3..5\right]\right)$

$G≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 3\; vertices\; and\; 3\; edges}$

$\mathrm{Meetings}≔\left[9..11.5\,9.5..10\,9.75..15\,11.5..15\,12.5..13.5\,14.5..17\,16.5..17.5\right]$

$\mathrm{Meetings}≔\left[9..11.5\,9.5..10\,9.75..15\,11.5..15\,12.5..13.5\,14.5..17\,16.5..17.5\right]$

$\mathrm{RoomNames}≔\left[''Suite\; Infinity''\,''Geddes\; Suite''\,''Taylor\text{'}s\; Suite''\right]$

$\mathrm{RoomNames}≔\left[''Suite\; Infinity''\,''Geddes\; Suite''\,''Taylor\text{'}s\; Suite''\right]$

$\mathrm{Schedule}≔\mathrm{GreedyColor}\left(\mathrm{IntervalGraph}\left(\mathrm{Meetings}\right)\right)$

$\mathrm{Schedule}≔3,\left[1\,2\,0\,2\,1\,1\,0\right]$

$\mathrm{Room}≔i\mapsto \mathrm{RoomNames}\left[\mathrm{Schedule}\left[2\right]\left[\mathrm{ListTools}:-\mathrm{Search}\left(i\,\mathrm{Meetings}\right)\right]+1\right]\:$

$\mathrm{ListTools}:-\mathrm{Classify}\left(\mathrm{Room}\,\mathrm{Meetings}\right)$

$table\left(\left[''Suite\; Infinity''=\left\{9.75..15\,16.5..17.5\right\}\,''Geddes\; Suite''=\left\{9..11.5\,12.5..13.5\,14.5..17\right\}\,''Taylor\text{'}s\; Suite''=\left\{9.5..10\,11.5..15\right\}\right]\right)$

$\mathrm{IntervalGraph}\left(\left[\mathrm{RealRange}\left(-1\,\mathrm{Open}\left(0\right)\right)\,0..1\,1..2\right]\right)$

$\mathrm{Graph\; 2:\; an\; undirected\; graph\; with\; 3\; vertices\; and\; 1\; edge}$

$G≔\mathrm{IntervalGraph}\left(\left[0..8\,1..\mathrm{\pi }\,\exp \left(1\right)..20\,7..18\,11..14\,\mathrm{RealRange}\left(17\,\mathrm{Open}\left(23\right)\right)\,23..25\right]\right)$

$G≔\mathrm{Graph\; 3:\; an\; undirected\; graph\; with\; 7\; vertices\; and\; 9\; edges}$

$\mathrm{DrawGraph}\left(G\right)$

$\mathrm{IsIntervalGraph}\left(G\right)$

$\mathrm{true}$

The GraphTheory[IntervalGraph] command was introduced in Maple 2016.

For more information on Maple 2016 changes, see Updates in Maple 2016 .

The GraphTheory[IntervalGraph] command was updated in Maple 2020.

The GraphTheory[IsIntervalGraph] command was introduced in Maple 2022.

For more information on Maple 2022 changes, see Updates in Maple 2022 .