Answers are grounded in this paper and cite their sources.
In this paper, we use crossing number and wire area arguments to find lower bounds on the layout area and maximum edge length of a variety of computationally useful networks. In particular, we describe 1) an N-node planar graph which has layout area Θ(NlogN), and maximum edge length Θ(N1/2/log1/2N), 2) an N-node graph with an O(N1/2)-separator which has layout area Θ(Nlog2N) and maximum edge length Θ(N1/2logN/loglogN), and 3) an N-node graph with an O(N1-1/r)-separator which has maximum edge length Θ(N1-1/r) for any r ≥ 3.
No takes yet. Share an insight, caveat, or question.
Frank Thomson Leighton (1981) studied this question.