Planar graph decomposition and all pairs shortest paths

ABSTRACT

An algorithm is presented for generating a succinct encoding of all pairs shortest path information in a directed planar graph G with real-valued edge costs but no negative cycles. The algorithm runs in O(pn) time, where n is the number of vertices in G, and p is the minimum cardinality of a subset of the faces that cover all vertices, taken over all planar embeddings of G. The algorithm is based on a decomposition of the graph into O(pn) outerplanar subgraphs satisfying certain separator properties. Linear-time algorithms are presented for various subproblems including that of finding an appropriate embedding of G and a corresponding face-on-vertex covering of cardinality O(p), and of generating all pairs shortest path information in a directed outerplannar graph.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: BAKER, B. S. Approximation algorithms for NP-complete problems on planar graphs (prehmirmry version). In Proceedings of the 24th IEEE Symposium on Foundations of Computer Science (Tucson). IEEE, New York. 1983, pp. 265-273.
• 3: Daniel Bienstock , Clyde L. Monma, On the complexity of covering vertices by faces in a planar graph, SIAM Journal on Computing, v.17 n.1, p.53-76, Feb. 1988 [doi>10.1137/0217004]
• 4: BOOTH, K. S., AND LUEKER, G. S. Testing for the consecutive ones property, interval graphs, and graph plananty using PQ-tree algorithms. J. Comput. Syst. Sci 13(1976), 335-379.
• 5: DEO, N., AND PANG, C. Shortest-path algorithms: Taxonomy and annotation. Networks 14 (1984). 275-323.
• 6: DIJKSTRA, E. W. A note on two problems in connexion with graphs. Numerische Math, 1 (1959). 269-271.
• 7: EVEN, S., AND TARJAN. R. E. Computing an st-numbenng. Theor. Comput, Sci. 2 (1976), 339-344.
• 8: M. R. Fellows , M. A. Langston, Nonconstructive advances in polynomial-time complexity, Information Processing Letters, v.26 n.3, p.155-162, Nov. 23, 1987
• 9: Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
• 10: Greg N. Frederickson, Implicit Data Structures for the Dictionary Problem, Journal of the ACM (JACM), v.30 n.1, p.80-94, Jan. 1983 [doi>10.1145/322358.322364]
• 11: Greg N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM Journal on Computing, v.16 n.6, p.1004-1022, December 1, 1987 [doi>10.1137/0216064]
• 12: FREDERICKSON, G. N., AND JANARDAN, R. Designing networks with compact routing tables. Algorithmica 3 (1988), 171-190.
• 13: Greg N. Frederickson , Ravi Janardan, Efficient message routing in planar networks, SIAM Journal on Computing, v.18 n.4, p.843-857, Aug. 1989 [doi>10.1137/0218058]
• 14: FREDMAN, M. L. New bounds on the complexity of the shortest path problem. SIAM J. Comput 5 (1976), 83-89.
• 15: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• 16: H Gajewska , R E Tarjan, Deques with heap order, Information Processing Letters, v.22 n.4, p.197-200, April 1986 [doi>10.1016/0020-0190(86)90028-1]
• 17: HARARY, F. Graph Theory. Addison-Wesley, Reading Mass., 1969.
• 18: HOPCROFT, J. E., AND TARJAN, R. E. Dividing a graph into triconnected components. SIAM J. Comput 2(1973), 135-158.
• 19: John Hopcroft , Robert Tarjan, Efficient Planarity Testing, Journal of the ACM (JACM), v.21 n.4, p.549-568, Oct. 1974 [doi>10.1145/321850.321852]
• 20: MUNRO, J. I., AND SUWANDA, H. Implicit data structures for fast search and update. J. Comput. Syst. Sci. 21 (1980), 236-250.
• 21: SANTORO, N., AND KHATIB, R. Labelling and implicit routing inf networks Comput J. 28 (1985), 5-8.
• 22: VAN LEEUWEN, J., AND TAN, R. B. Computer networks with compact routing tables. In G. Rosenberg and A. Salomaa, Eds. The Book of L. Springer-Verlag, New York, 1986. pp. 259-273.
• 23: Stephen Warshall, A Theorem on Boolean Matrices, Journal of the ACM (JACM), v.9 n.1, p.11-12, Jan. 1962 [doi>10.1145/321105.321107]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms

Keywords:
NP-completeness, all pairs shortest paths, approximation algorithm, compact routing table, graph embedding, outerplanar graph, planar graph, succinct encoding