20 citations · 66 across the 52 of their papers we have counts for
4 papers · 1 filter
Spanners of Complete -Partite Geometric Graphs
Prosenjit Bose, Paz Carmi, Mathieu Couture +3
We address the following problem: Given a complete -partite geometric graph whose vertex set is a set of points in , compute a spanner of that has a ``…
Geometric Spanners With Small Chromatic Number
Prosenjit Bose, Paz Carmi, Mathieu Couture +3
Given an integer , we consider the problem of computing the smallest real number such that for each set of points in the plane, there exists a -spanner f…
On a family of strong geometric spanners that admit local routing strategies
Prosenjit Bose, Paz Carmi, Mathieu Couture +2
We introduce a family of directed geometric graphs, denoted $\paz$, that depend on two parameters and . For and , the $\paz$ graph is a str…
Sparse geometric graphs with small dilation
Boris Aronov, Mark de Berg, Otfried Cheong +4
Given a set S of n points in R^D, and an integer k such that 0 <= k < n, we show that a geometric graph with vertex set S, at most n - 1 + k edges, maximum degree five, and dilatio…