Premium
Constructions of large planar networks with given degree and diameter
Author(s) -
Fellows M.,
Hell P.,
Seyffarth K.
Publication year - 1998
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199812)32:4<275::aid-net4>3.0.co;2-g
Subject(s) - degree (music) , planar , mathematics , combinatorics , upper and lower bounds , planar graph , discrete mathematics , computer science , graph , physics , mathematical analysis , computer graphics (images) , acoustics
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) 12 k Δ ⌊ 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