Modelarea “structurii liniare” care este prezentă în mai multe sisteme, precum rețelele trofice, problemele de alocare a resurselor și ADN-ul, are la bază grafurile de interval (grafuri intersecție a unor intervale de pe o linie dreapta). Totodată, având în vedere că mulțimile de date reale pot conține greșeli și zgomot, este nevoie de a extinde rezultatele algoritmice obținute pentru grafurile de interval la unele clase de grafuri mai generale. Această problematică este abordată în contextul calculării excentricităților, datorită importanței acestora privind clasificarea nodurilor unei rețele. O astfel de generalizare este obținută de la grafurile de interval până la grafurile interval+ (obținute prin adăugarea a noduri într-un graf de interval). În special, un algoritm care rulează în timp cvasiliniar, pentru orice valoare fixată, este propus. Până în prezent, timpul de rulare al celui mai bun algoritm pentru această problema era cvadratic în numărul de noduri (Bentert & Nichterlein, 2022). Cu toate aceasta, este demonstrat sub unele ipoteze standard de complexitate că o astfel de generalizare nu este posibilă pentru grafurile al cărui număr de interval este limitat la o constantă.