Broadcasting in planar graphs.
Pavol Hell, Karen Seyffarth · 1998
For an arbitrary graph on n vertices, the minimum time required to broadcast is pogz n 1, and for any n, there exist graphs on n vertices with broadcast time equal to fIogz n 1. When restricted to planar graphs, this is generally not the case; however, just one additional time unit is sufficient to allow broadcasting in certain planar graphs. We also show that the maximum number of vertices in a planar graph with broadcast time t is at least 2 t- 1 + 2 LU/3J + 1.