Listing all the minimal separators of a planar graph.

Frédéric Mazoit (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

I present an efficient algorithm which lists the minimal separators of a planar graph in O(n) per separator.

Je présente un algorithme d’´enumération des séparateurs minimaux des graphes planaires dont la complexité est O(n) par séparateur.

Mots clés: Minimal Separator Enumeration; Planar Graphs

Mots clés: graphes planaires; séparateurs minimaux; énumération

Domaines: Informatique [cs]

Frédéric Mazoit. Listing all the minimal separators of a planar graph.. [Research Report] LIP RR-2004-35, Laboratoire de l'informatique du parallélisme. 2004, 2+10p. ⟨hal-02102065⟩