Grafo convesso

Il grafo convesso è definito come segue. Tenendo presente la definizione di grafo bipartito:

Proprietà di Adiacenza

Sia $G=⟨X,Y,E⟩$ un grafo bipartito. Un ordinamento di X ha la “proprietà di adiacenza”, se per ogni $y\in Y$, i vicini di y in X sono consecutivi nell'ordinamento di X.

Grafo Convesso

Un grafo bipartito $G=⟨X,Y,E⟩$ è “convesso ”, se c'è un ordinamento di X o di Y che rispetta la proprietà di adiacenza.