Constructions of large planar networks with given degree and diameter
Michael R. Fellows, Pavol Hell, Karen Seyffarth · Networks · 1998
There is considerable interest in constructing large networks with given diameter and maximum degree. In certain applications, there is a natural restriction for the networks to be planar. Thus, consider the problem of determining the maximum number of nodes in a planar network with maximum degree Δ and diameter at most k. We have previously proved that this number is at most (roughly) 12kΔ⌊k/2⌋ and there is a trivial lower bound of about (Δ − 1)⌊k/2⌋. We introduce a number of general constructions which substantially improve the lower bound and yield the largest known networks. We also provide a catalog of the best-known networks for small values of Δ and k, many obtained by specialized constructions. © 1998 John Wiley & Sons, Inc. Networks 32:275–281, 1998