On two dual classes of planar graphs (Q916681): Difference between revisions

A \(\Delta\) is a cycle of 3 edges and a Y is a degree-3 vertex and its incident edges. It is shown in [\textit{G. V. Epifanov}, Reduction of a plane graph to an edge by a star-triangle transformation, Dokl. Akad. Nauk SSSR 166, 19-22 (1966; Zbl 0149.213)] that any connected planar graph can be reduced to an edge by a sequence of Y-\(\Delta\) reductions (replacing a Y by a \(\Delta\)), \(\Delta\)-Y reductions replacing a \(\Delta\) by a Y), series reductions (homeomorphic removal of a degree-2 vertex), parallel reductions (deletion of one of a set of parallel edges), and degree-1 reductions (deletion of a degree-1 vertex and its incident edge). A \(\Delta\)-Y graph is a planar graph reducible to an edge via \(\Delta\)-Y, series, parallel and degree-1 reductions, with an analogous definition for a Y-\(\Delta\) graph. It is shown here that a 2-connected planar graph is a \(\Delta\)-Y if and only if its planar dual is a Y- \(\Delta\) graph. The \(\Delta\)-Y graphs were characterized in [\textit{T. Politof}, A characterization and efficient reliability computation of \(\Delta\)-Y reducible networks, Ph. D. Thesis, University of California, Berkeley (1983)] as having no subgraph homeomorphic to \(C_{4,4}\) (a cube) or \(W_{2,5}\) (the planar dual of a pentagonal prism). Here, these graphs are characterized as having no minor isomorphic to \(C_{4,4}\) or \(W_{2,5}\) (where a minor of a graph G is a graph obtained from G by deleting some edges and contracting others to a vertex), and the Y- \(\Delta\) graphs are characterized as having no minor isomorphic to \(C_{5,5}\) (a pentagonal prism) or \(W_{2,4}\) (an octahedron). The result for Y-\(\Delta\) graphs specializes to planar graphs a characterization in [\textit{S. Arnborg}, \textit{A. Proskurowski} and \textit{D. Corneil}, Forbidden minors characterization of partial 3-trees, Technical Report CIS-TR-86-07, Dept. of Computer and Information Science, University of Oregon; see also the same authors' paper with the same title in Discrete Math. 80, No.1, 1-19 (1990; Zbl 0701.05016)] of partial 3-trees as having no minor isomorphic to \(C_{5,5}\), \(W_{2,4}\), and 2 other, non-planar, graphs, since Y-\(\Delta\) graphs are just planar partial 3-trees, and the result for \(\Delta\)-Y graphs follows by duality. In addition, linear-time algorithms are presented for recognizing these 2 classes of graphs, and for embedding \(\Delta\)-Y graphs in k-trees for \(k=1,2,3,4\).