Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-28T17:07:31.768Z Has data issue: false hasContentIssue false
  • English
  • Français

Shortcutting Planar Digraphs*

Published online by Cambridge University Press:  12 September 2008

Mikkel Thorup
Mikkel Thorup
Affiliation:
Department of Computer Science, University of Copenhagen, Universitetsparken 1, 2100 København Ø, Denmark; e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper presents a constructive proof that for any planar digraph G on p vertices, there exists a subset S of the transitive closure of G such that the number of arcs in S is less than or equal to the number of arcs in G, and such that the diameter of G∪S is O(α(p, p)(log p)2). Here the diameter refers to the maximum distance from a vertex υ to a vertex w where (υ, w) is from the transitive closure of G – which is also the transitive closure of G ∪ S. This result provides support for the author's previous conjecture that such a set S achieving a diameter polylogarithmic in the number of vertices exists for any digraph. The result also adresses an open question of Chazelle, who did some related work on trees, and suggested the generalization to the planar cases.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 4 , Issue 3 , September 1995 , pp. 287 - 315
Copyright
Copyright © Cambridge University Press 1995

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Bonet, M. L. and Buss, S. R. (1991) On the deduction rule and the number of proof lines. Proc. 6th Ann. IEEE Symposium on Logic in Computer Science, 286–297.CrossRefGoogle Scholar
[2]Bodlaender, H., Tel, G. and Santoro, N. (1994) Trade-Offs in Non-Reversing Diameter. Nordic J. Comput. 1(1) 111–134.Google Scholar
[3]Chartrand, G. and Lesniak, L. (1986) Graphs & Digraphs, 2nd ed.Wadsworth & Brooks / Cole Advanced Books & Software.Google Scholar
[4]Chazelle, B. (1987) Computing on a free tree via complexity preserving mappings. Algorithmica 2 337–361.CrossRefGoogle Scholar
[5]Gilbert, J. R., Hutchinson, J. P. and Tarjan, R. E. (1984) A separator theorem of graphs of bounded genus. J. Algorithms 5 391–407.CrossRefGoogle Scholar
[6]Kao, M. and Klein, P. N. (1990) Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs. Proc. 22nd Ann. ACM Symposium on Theory of Computing, ACM Press, New York, 181–192.Google Scholar
[7]Karp, R. and Ramachandran, V. (1990) Parallel algorithms for shared-memory machines. In: van Leeuwen, J. (ed.), Handbook of Theoretical Computer Science. North-Holland.Google Scholar
[8]Lingas, A. (1990) Efficient parallel algorithms for path problems in planar directed graphs. Proc. SIGAL'90. Springer-Verlag, LNCS 450, 447–457.Google Scholar
[9]Loebl, M. Personal communication.Google Scholar
[10]Lipton, R. J. and Tarjan, R. E. (1979) A separator theorem for planar graphs. SIAM J. Appl. Math. 36 177–189.CrossRefGoogle Scholar
[11]Santoro, N. (1988) (Time × space)-efficient implementations of hierachical conceptual models. In: van Leeuwen, J. (ed.), Proc. 14th Int. Workshop on Graph-Theoretic Concepts in Computer Science. Springer-Verlag, LNCS 334, 180–189.Google Scholar
[12]Robertson, N. and Seymour, P. D. (1986) Graph minors V: excluding a planar graph. J. Combinatorial Theory, Ser. B. 22 92–114.CrossRefGoogle Scholar
[13]Robertson, N. and Seymour, P. D. Graph minors XVII: excluding a non-planar graph. Submitted for publication.Google Scholar
[14]Tarjan, R. E. (1972) Depth first search and linear graph algorithms. SIAM J. Computing 1(2) 146–160.CrossRefGoogle Scholar
[15]Tarjan, R. E. (1975) Efficiency of a good but not linear set union algorithm. J. ACM 22 215–225.CrossRefGoogle Scholar
[16]Thorup, M. (1993) On shortcutting digraphs. In: Mayr, E. (ed.), Proc. 18th Int. Workshop on Graph-Theoretic Concepts in Computer Science. Springer-Verlag, LNCS 657, 205–211.CrossRefGoogle Scholar
[17]Yao, A. C. (1982) Space-time tradeoff for answering range queries. Proc. 14th Ann. ACM Symposium on Theory of Computing. ACM Press, New York, 128–136.Google Scholar