diff --git a/tmf/org.eclipse.tracecompass.tmf.analysis.xml.ui/src/org/eclipse/tracecompass/internal/tmf/analysis/xml/ui/views/timegraph/XmlPresentationProvider.java b/tmf/org.eclipse.tracecompass.tmf.analysis.xml.ui/src/org/eclipse/tracecompass/internal/tmf/analysis/xml/ui/views/timegraph/XmlPresentationProvider.java
index f848f1a..57659a9 100644
--- a/tmf/org.eclipse.tracecompass.tmf.analysis.xml.ui/src/org/eclipse/tracecompass/internal/tmf/analysis/xml/ui/views/timegraph/XmlPresentationProvider.java
+++ b/tmf/org.eclipse.tracecompass.tmf.analysis.xml.ui/src/org/eclipse/tracecompass/internal/tmf/analysis/xml/ui/views/timegraph/XmlPresentationProvider.java
@@ -15,9 +15,10 @@ package org.eclipse.tracecompass.internal.tmf.analysis.xml.ui.views.timegraph;
 
 import java.util.ArrayList;
 import java.util.Collections;
-import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
+import java.util.NavigableMap;
+import java.util.TreeMap;
 
 import org.eclipse.jdt.annotation.NonNull;
 import org.eclipse.swt.graphics.GC;
@@ -55,9 +56,10 @@ public class XmlPresentationProvider extends TimeGraphPresentationProvider {
     private List<StateItem> stateValues = new ArrayList<>();
     /*
      * Maps the value of an event with the corresponding index in the
-     * stateValues list
+     * stateValues list; if no definition for this value, maps to "floor" key,
+     * that is, the highest key <= index.
      */
-    private Map<Integer, Integer> stateIndex = new HashMap<>();
+    private NavigableMap<Integer, Integer> stateIndex = new TreeMap<>();
 
     @Override
     public int getStateTableIndex(ITimeEvent event) {
@@ -69,9 +71,12 @@ public class XmlPresentationProvider extends TimeGraphPresentationProvider {
 
             if (entry.getType() == EntryDisplayType.DISPLAY) {
                 // Draw state only if state is already known
-                Integer index = stateIndex.get(value);
-                if (index != null) {
-                    return index;
+                Integer key = stateIndex.floorKey(value);
+                if (key != null) {
+                    Integer index = stateIndex.get(key);
+                    if (index != null) {
+                        return index;
+                    }
                 }
             }
         }
@@ -92,10 +97,13 @@ public class XmlPresentationProvider extends TimeGraphPresentationProvider {
             int value = tcEvent.getValue();
 
             if (entry.getType() == EntryDisplayType.DISPLAY) {
-                Integer index = stateIndex.get(value);
-                if (index != null) {
-                    String rgb = stateValues.get(index.intValue()).getStateString();
-                    return rgb;
+                Integer key = stateIndex.floorKey(value);
+                if (key != null) {
+                    Integer index = stateIndex.get(key);
+                    if (index != null) {
+                        String rgb = stateValues.get(index.intValue()).getStateString();
+                        return rgb;
+                    }
                 }
             }
             return null;