Shortest Path Computations in S-Graphs
Greg N. Frederickson, Susanne E. Hambrusch, Hung-Yi Tu · Purdue e-Pubs (Purdue University System) · 1991
We consider a class of non-planar graphs that arises in VLSI layout compaction and show that a number of shortest path problems on these graphs can be solved in the same time as the corresponding problem in a planar graph.