Listing all the minimal separators of a 3-connected 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 3-connected planar graph in $O(n)$ per separator.

Je présente un algorithme d'éumération des séparateurs minimaux des graphes planaires 3-connexes dont la complexité est O(n) par séparateur.

Mots clés: 3-Connected Planar Graphs

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

Domaines: Informatique [cs]

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