On perfect plane near triangulations

Abstract

A plane embedding of a (planar) graph G is called a plane near-triangulation if the newlineboundary of every face of G, except possibly the outer face, is a cycle of length newlinethree. A plane near-triangulation G can be decomposed into a collection of induced newline newlinesubgraphs, described here as the W-components of G, such that G is perfect (re- newlinespectively, chordal) if and only if each of its W-components is perfect (respectively, newline newlinechordal). Each W-component is a 2-connected plane near-triangulation, free of edge newlineseparators and separating triangles. Graphs satisfying these conditions will be called newlineW-near-triangulations. A linear time decomposition of G into its W-components is newlineachievable using a combination of known techniques from the literature. newlineW-near-triangulations have the property that the open neighbourhood of every newlineinternal vertex induces a cycle. It follows that a W-near-triangulation H of at least newlinefive vertices is non-chordal if and only if it contains an internal vertex. This yields a newlinelocal structural characterization that a plane near-triangulation G is chordal if and newlineonly if it does not contain an induced wheel of at least five vertices. newlineFor W-near-triangulations that are free of induced wheels of five vertices, we newlinederive a similar local criteria, that depends only on the neighbourhoods of individual newlinevertices and faces, for checking perfectness. We show that a W-near-triangulation newlineH that is free of any induced wheel of five vertices is perfect if and only if there newlineexists neither an internal vertex x, nor a face f such that, the neighbours of x or f newlineinduces an odd hole. The above characterization leads to a linear time algorithm for newlinedetermining perfectness of this class of graphs. newlineFinally, we generalize the above result to derive a local criterion for perfect newlineplane near-triangulated graphs. newline