The layout of the underplanes is such that the highest vertex on the staircase has its underplanes
immediately below the lowest vertex on the staircase. The underplanes form a parallel staircase to the main
staircase formed by
the vertices themselves.
Each underplane's length is from its associated vertex to the last vertex
in the graph. Thus the underplanes of the last vertex n have length 0 and are not used.
This layout allows a pillar from a vertex V to drop straight to either of its underplanes without crossing a
lane since all the underplanes that the pillar drops through can not have routings on them (their vertices are higher up
the staircase and thus the underplane is shorter). This allows the pillar to bend directly into a lane which is not possible
on the other routings. This is the crux of the 5 bend model but it is also what causes insertions and deletions to cost
O(n) time.
When a vertex is inserted, all vertices lower than the inserted vertex must have their underplanes slide down.
This results in
up to 3 edges per vertex being lengthened in their vertical direction. The shape of the graph does not change, nor do the routings to
their vertices, only the length of some edges is increased.
When a routing that uses the underplanes reaches its destination vertex W, it then routes across to the
North pillar of W. This will not result in any crossings since each lane is routed on a different plane and
only one lane can route to W's North pillar.
The special case of use of the underplanes is by the Bottom Port when it is routing to the Top or South ports
of W. It drops to the East underplane of V and crosses under the S pillar of V which ends one plane above. It then
routes up the Bottom Climb to get to its final destination. This routing does not cross the South pillar which
ends one plane above it. It also does not cross the East to North lane of the East underplane of V since this lane does not exist at this point (
it comes into being 2 units to the East of the bottom pillar and runs east from that point.)
The Bottom to South routing could use the South pillar of W but this was not chosen. It would reduce the average edge length
of this routing but would cause it to vary in its routing from all the other routings that go to the South Port of W.
|