Red-Black Spanners for Mixed-Charging Vehicular Networks

Motivated by the recent trend of increasing number of e-cars and hybrid cars, we investigate the problem of building a red-black spanner for a mixed-charging vehicular network. In such a network, we have two kinds of gas/charging stations: electric (black) and the traditional gas (red) stations. Our requirement is that one cannot connect two gas stations directly in the spanner (i.e., no red-red edge), and our goal is to build a linear-size spanner with a bounded stretch factor under this requirement. (In 2-d, it can be shown that a spanner with an optimal stretch factor could have a quadratic size and if one is restricted to build the spanner purely from a given road network then it is impossible to obtain a bounded stretch factor.) Our main results are summarized as follows.