Shortcutting Planar Digraphs

DOI10.1017/S0963548300001668MaRDI QIDQ4862749zbMATH OpenFDO

Authors 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) Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12)

Recommendations

• scientific article; zbMATH DE number 512931
• Faster shortest-path algorithms for planar graphs
• Faster shortest-path algorithms for planar graphs
• Shorter Labeling Schemes for Planar Graphs
• Shorter Labeling Schemes for Planar Graphs
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Shortest path queries in planar graphs
• Planar Digraphs
• scientific article; zbMATH DE number 6850313
• Short encodings of planar graphs and maps

Cites work

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

Cited in

(11)

• scientific article; zbMATH DE number 2079397 (Why is no real title available?)
• scientific article; zbMATH DE number 7238981 (Why is no real title available?)
• Steiner transitive-closure spanners of low-dimensional posets
• scientific article; zbMATH DE number 6850313 (Why is no real title available?)
• Efficient provably-secure hierarchical key assignment schemes
• Transitive-closure spanners: a survey
• A hierarchy of lower bounds for sublinear additive spanners
• scientific article; zbMATH DE number 7561636 (Why is no real title available?)
• Shorter Labeling Schemes for Planar Graphs
• Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts
• Shortcutting directed and undirected networks with a degree constraint

This page was built for publication: Shortcutting Planar Digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4862749)