Shortcutting Planar Digraphs

DOI10.1017/S0963548300001668zbMath0839.05044MaRDI QIDQ4862749

Mikkel Thorup

Publication date: 5 June 1996

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

zbMATH Keywords

planar digraphshortcuttinglogarithmic diameter

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20)

Related Items (8)

A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Steiner transitive-closure spanners of low-dimensional posets ⋮ Shortcutting directed and undirected networks with a degree constraint ⋮ Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts ⋮ Transitive-Closure Spanners: A Survey ⋮ Efficient provably-secure hierarchical key assignment schemes ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• Graph minors. V. Excluding a planar graph
• Computing on a free tree via complexity-preserving mappings
• A separator theorem for graphs of bounded genus
• A Separator Theorem for Planar Graphs
• Efficiency of a Good But Not Linear Set Union Algorithm
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: Shortcutting Planar Digraphs