ISSN : 1796-2056
Volume : 3    Issue : 2    Date : February 2008

Time Efficient Radio Broadcasting in Planar Graphs
Fredrik Manne and Qin Xin
Page(s): 9-16
Full Text:
PDF (374 KB)

We study the communication primitive of broadcasting (one-to-all communication) in known
topology radio networks, i.e., where for each primitive the schedule of transmissions is
precomputed based on full knowledge about the size and the topology of the network. We show that
radio broadcasting can be completed in
D + O(log n) time units in planar graphs of size n, and with
D. This improves the currently best known D+O(log3 n) time schedule proposed by Elkin
and Kortsarz in [16] [SODA’05], and 3
D time schedule due to G ˛ asieniec, Peleg and Xin in [23]
[PODC’05]. In this paper, we also explore broadcasting in radio networks in the presence of edge

Index Terms
Broadcasting, centralized radio networks, fault-tolerance, gossiping, planar graphs.