𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On terminal delta-wye reducibility of planar graphs

✍ Scribed by Isidoro Gitler; Feliú Sagols

Publisher
John Wiley and Sons
Year
2011
Tongue
English
Weight
614 KB
Volume
57
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

We prove terminal -Y reducibility of planar graphs with at most three terminals. The most important consequence of our proof is that this implicitly gives an efficient algorithm with time complexity O(|E (G)| 4 ) for reducibility of planar graphs G with at most three terminals. It also can be used for restricted reducibility problems with more terminals. Our proof uses a very well-known translation from these operations to transformations on the medial graph.

📜 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 delta-wye reduction for planar gr
On the delta-wye reduction for planar graphs
✍ K. Truemper 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 367 KB

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

On the minimal reducible bound for outer
On the minimal reducible bound for outerplanar and planar graphs
✍ Peter Mihók 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 223 KB

Let L be the set of all additive and hereditary properties of graphs. For P1, P2 E L we define the reducible property R = P1P2 as follows: G E PtP2 if there is a bipartition (V~,/1"2) of V(G) such that (V~) E Pi and (V2) E P2. For a property P E L, a reducible property R is called a minimal reducibl