IMSc Webinar

Determining perfectness of maximal planar graph in quadratic time.

Sameera Salam

IMSc

Webinar: join at https://zoom.us/j/95566670601?pwd=cmEvV1REeXk4UFFnWTAwK0xIaVhQZz09 We present a simple structural local characterization for perfect maximal planar graphs which helps to design an improved quadratic time for its recognition. A maximal planar graph is a drawing of a planar graph such that every face is a triangle. A graph is perfect if for each of its induced subgraphs, the chromatic number and the clique numbers are the same. It is known that a planar graph G is perfect if and only if it is odd hole-free. We show that a maximal planar graph G is not perfect if and only if it has a vertex subset X that is a vertex or end points of an edge or a triangle, and the vertices on the exterior face of the local neighbourhood of which, induces an odd hole.