On graphs preserving rectilinear shortest paths in the presence of obstacles

R.K. Ahuja, K. Mehlhorn, J.B. Orlin and R.E. Tarjan, Faster algorithms for the shortest path problem, J. ACM 37(1990)213–223.

T. Asano, T. Asano, L. Guibas, J. Hershberger and H. Imai, Visibility of disjoint polygons, Algorithmica 1(1986)49–63.

K.L. Clarkson, S. Kapoor and P.M. Vaidya, Rectilinear shortest paths through polygonal obstacles inO(n(logn)2) time,Proc. 3rd Annual Symp. on Computational Geometry (1987), pp. 251–257.

K.L. Clarkson, S. Kapoor and P.M. Vaidya, Rectilinear shortest paths through polygonal obstacles inO(n(logn)3/2) time, Manuscript (1988).

P.J. de Rezende, D.T. Lee and Y.F. Wu, Rectilinear shortest paths in the presence of rectangular barriers, Discr. Comp. Geometry 4(1989)41–53.

M.L. Fredman and R.E. Tarjan, Fibronacci heaps and their uses in improved network optimization algorithms, J. ACM 34(1987)596–615.

H.N. Gabow, Scaling algorithms for network problems, J. Comp. Syst. Sci. 31(1985)148–168.

M.R. Garey, R.L. Graham and D.S. Johnson, The complexity of computing Steiner minimal trees, SIAM J. Appl. Math. 32(1977)835–859.

F.O. Hadlock, A shortest path algorithm for grid graphs, Networks 7(1977)323–334.

D.B. Johnson, A priority queue in which initialization and queue operations takeO(log logD) time, Math. Syst. Theory 15(1982)295–309.

S. Kapoor and S.N. Maheshwari, Efficient algorithms for Euclidean shortest path and visibility problems with polygonal obstacles,Proc. 4th Annual Symp. on Computational Geometry (1988), pp. 172–182.

J.S.B. Mitchell, Shortest rectilinear paths among obstacles,1st Int. Conf. on Industrial and Applied Mathematics (1987); also as Technical Report, Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands.

H. Mori, T. Fujita, H. Wakata and S. Goto, WIREX: VLSI wiring design expert system,Proc. IFIP VLSI 85 (1985), pp. 297–306.

M. Overmars and E. Welzl, New methods for computing visibility graphs,Proc. 4th Annual Symp. on Computational Geometry (1988), pp. 164–171.

F.P. Preparata and M.I. Shamos,Computational Geometry: An Introduction (Springer, 1985).

G. Reich and P. Widmayer, Beyond Steiner's problem: A VLSI oriented generalization,Int. Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 411 (Springer, 1989), pp. 196–210.

J.D. Ullman,Computational Aspects of VLSI (Computer Science Press, 1984).

E. Welzl, Constructing the visibility graph forn line segments inO(n 2) time, Inf. Proc. Lett. 20(1985)167–171.

P. Widmayer and C.K. Wong, An optimal algorithm for the maximum alignment of terminals, Inf. Proc. Lett. 30(1985)75–82.

P. Widmayer, L.S. Woo and C.K. Wong, Maximizing pin alignment in a semi-custom chip circuit layout, Integration 6(1988)3–33.

P. Widmayer, Y.F. Wu and C.K. Wong, On some distance problems in fixed orientations, SIAM J. Comp. 16(1987)728–746.

P. Winter, Steiner problems in networks: A survey, Networks 17(1987)129–167.

Y.F. Wu, P. Widmayer, M.D.F. Schlag and C.K. Wong, Rectilinear shortest paths and minimum spanning trees in the presence of rectilinear obstacles, IEEE Trans. Comp. C-36(1987)321–331.