Abstract | ||
---|---|---|
A graph is YΔY-reducible if it can bereduced to a vertex by a sequence of series-parallel reductions andYΔY-transformations. Terminals aredistinguished vertices, that cannot be deleted by reductions andtransformations. In this article, we show that four-terminal planargraphs are YΔY-reducible when at least three ofthe vertices lie on the same face. Using this result, wecharacterize YΔY-reducible projective-planargraphs. We also consider terminals in projective-planar graphs, andestablish that graphs of crossing-number one areYΔY-reducible. © 2000 John Wiley &Sons, Inc. J Graph Theory 33: 8393, 2000 |
Year | DOI | Venue |
---|---|---|
2000 | 10.1002/(SICI)1097-0118(200002)33:2<>1.0.CO;2-1 | Journal of Graph Theory |
Keywords | Field | DocType |
wecharacterize y,y-reducible projective-planargraphs,reductions andtransformations,four-terminal reducibility,four-terminal planargraphs,inc. j graph theory,series-parallel reductions andy,projective-planar graph,terminals aredistinguished vertex,projective-planar wye-delta-wye-reducible graph,john wiley,ofthe vertex,wye delta,planar graph,series parallel | Discrete mathematics,Topology,Combinatorics,Indifference graph,Clique-sum,Chordal graph,Book embedding,Pathwidth,1-planar graph,Metric dimension,Pancyclic graph,Mathematics | Journal |
Volume | Issue | Citations |
33 | 2 | 9 |
PageRank | References | Authors |
0.83 | 13 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Dan Archdeacon | 1 | 277 | 50.72 |
Charles J. Colbourn | 2 | 2726 | 290.04 |
Isidoro Gitler | 3 | 29 | 7.03 |
J. Scott Provan | 4 | 678 | 90.11 |