Ein Graph ${\displaystyle {}G=(V,E)}$ heißt linear, wenn es eine Auflistung ${\displaystyle {}v_{1},\ldots ,v_{n}}$ aller Knoten derart gibt, dass die Kantenmenge gleich ${\displaystyle {}\{v_{i},v_{i+1}\}}$, ${\displaystyle {}i=1,2,\ldots ,n-1}$, ist.