✦ LIBER ✦

On the delta-wye reduction for planar graphs

✍ Scribed by K. Truemper

Publisher: John Wiley and Sons
Year: 1989
Tongue: English
Weight: 367 KB
Volume: 13
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190130202

No coin nor oath required. For personal study only.

✦ Synopsis

We provide an elementary proof of an important theorem by G. V. Epifanov, according to which every two-terminal planar graph satisfying certain connectivity restrictions can by some sequence of series/parallel reductions and delta-wye exchanges be reduced to the graph consisting of the two terminals and just one edge.

📜 SIMILAR VOLUMES

Four-terminal reducibility and projectiv

Four-terminal reducibility and projective-planar wye-delta-wye-reducible graphs

✍ Archdeacon, Dan; Colbourn, Charles J.; Gitler, Isidoro; Provan, J. Scott 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 188 KB

A graph is Y ∆Y -reducible if it can be reduced to a vertex by a sequence of series-parallel reductions and Y ∆Y -transformations. Terminals are dis-

On the linear arboricity of planar graph

On the linear arboricity of planar graphs

✍ Wu, Jian-Liang 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 188 KB 👁 2 views

The linear arboricity la(G) of a graph G is the minimum number of linear forests that partition the edges of G. Akiyama, Exoo, and Harary conjectured for any simple graph G with maximum degree ∆. The conjecture has been proved to be true for graphs having ∆ =

On the connectivity of maximal planar gr

On the connectivity of maximal planar graphs

✍ S. L. Hakimi; E. F. Schmeichel 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 254 KB 👁 1 views

A criterion for the planarity of a graph

✍ Jerome R. Breitenbach 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 146 KB 👁 1 views

In a recent paper, Carsten Thomassen [Carsten Thomassen, Planarity and duality of finite and infinite graphs. J. Combinatorial Theory Ser. B 29 (1980) 244-2711 has shown that a number of criteria for the planarity of a graph can be reduced to that of Kuratowski. Here we present another criterion whi

New upper bounds on the decomposability

New upper bounds on the decomposability of planar graphs

✍ Fedor V. Fomin; Dimitrios M. Thilikos 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 335 KB 👁 1 views

## Abstract It is known that a planar graph on __n__ vertices has branch‐width/tree‐width bounded by $\alpha \sqrt {n}$. In many algorithmic applications, it is useful to have a small bound on the constant α. We give a proof of the best, so far, upper bound for the constant α. In particular, for th

On the linear vertex-arboricity of a pla

On the linear vertex-arboricity of a planar graph

✍ K. S. Poh 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 153 KB 👁 2 views

## Abstract We prove in this note that the linear vertex‐arboricity of any planar graph is at most three, which confirms a conjecture due to Broere and Mynhardt, and others.