Shortcutting Planar Digraphs
Author:
- 12 September 1995
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 4 (3) , 287-315
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.Keywords
This publication has 7 references indexed in Scilit:
- On shortcutting digraphsLecture Notes in Computer Science, 1993
- Computing on a free tree via complexity-preserving mappingsAlgorithmica, 1987
- Graph minors. V. Excluding a planar graphJournal of Combinatorial Theory, Series B, 1986
- A separator theorem for graphs of bounded genusJournal of Algorithms, 1984
- A Separator Theorem for Planar GraphsSIAM Journal on Applied Mathematics, 1979
- Efficiency of a Good But Not Linear Set Union AlgorithmJournal of the ACM, 1975
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972