20080512
Spanners of complete kPartite geometric graphs
Publication
Publication
We address the following problem: Given a complete kpartite geometric graph K whose vertex set is a set of n points in ℝ d , compute a spanner of K that has a "small" stretch factor and "few" edges. We present two algorithms for this problem. The first algorithm computes a (5∈+∈ε)spanner of K with O(n) edges in O(n logn) time. The second algorithm computes a (3∈+∈ε)spanner of K with O(n logn) edges in O(n logn) time. Finally, we show that there exist complete kpartite geometric graphs K such that every subgraph of K with a subquadratic number of edges has stretch factor at least 3.
Additional Metadata  

dx.doi.org/10.1007/9783540787730_15  
Organisation  Computational Geometry Lab 
Bose, P, Carmi, P. (Paz), Couture, M. (Mathieu), Maheshwari, A, Morin, P, & Smid, M. (2008). Spanners of complete kPartite geometric graphs. doi:10.1007/9783540787730_15
