Shortcutting Planar Digraphs

DOI10.1017/S0963548300001668zbMATH Open0839.05044MaRDI QIDQ4862749FDOQ4862749

Authors: Mikkel Thorup 

Publication date: 5 June 1996

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

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

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)

Cites Work

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

Cited In (11)

• Steiner transitive-closure spanners of low-dimensional posets
• Title not available (Why is that?)
• Efficient provably-secure hierarchical key assignment schemes
• Transitive-closure spanners: a survey
• A hierarchy of lower bounds for sublinear additive spanners
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)

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)