In this paper, a new construct called connection graph, Gc, is proposed. An efficient geometric algorithm for constructing Gc is given, We present a framework for designing a class of time and space efficient maze-running and line-search rectilinear shortest path and rectilinear minimum spanning tree algorithms based on Gc . We give several example maze-running and line-search algorithms based on Gc to demonstrate the power of Gc in designing good sequential VLSI routing algorithms. No pagination in original publication.
