TY - CHAP
T1 - Blockers for noncrossing spanning trees in complete geometric graphs
AU - Keller, Chaya
AU - Perles, Micha A.
AU - Rivera-Campo, Eduardo
AU - Urrutia-Galicia, Virginia
N1 - Publisher Copyright:
© Springer Science+Business Media New York 2013. All rights are reserved.
PY - 2013/7/1
Y1 - 2013/7/1
N2 - In this chapter, we present a complete characterization of the smallest sets that block all the simple spanning trees (SSTs) in a complete geometric graph. We also show that if a subgraph is a blocker for all SSTs of diameter at most 4, then it must block all simple spanning subgraphs and, in particular, all SSTs. For convex geometric graphs, we obtain an even stronger result: Being a blocker for all SSTs of diameter at most 3 is already sufficient for blocking all simple spanning subgraphs.
AB - In this chapter, we present a complete characterization of the smallest sets that block all the simple spanning trees (SSTs) in a complete geometric graph. We also show that if a subgraph is a blocker for all SSTs of diameter at most 4, then it must block all simple spanning subgraphs and, in particular, all SSTs. For convex geometric graphs, we obtain an even stronger result: Being a blocker for all SSTs of diameter at most 3 is already sufficient for blocking all simple spanning subgraphs.
UR - http://www.scopus.com/inward/record.url?scp=84949176236&partnerID=8YFLogxK
U2 - 10.1007/978-1-4614-0110-0_20
DO - 10.1007/978-1-4614-0110-0_20
M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.chapter???
AN - SCOPUS:84949176236
SN - 1461401097
SN - 9781461401094
VL - 9781461401100
SP - 383
EP - 397
BT - Thirty Essays on Geometric Graph Theory
PB - Springer New York
ER -