Minimizing the Oriented Diameter of a Planar Graph

DOI10.1016/j.endm.2009.07.043zbMath1273.05052OpenAlexW2097160499MaRDI QIDQ2851475

Nicole Eggemann, Steven D. Noble

Publication date: 10 October 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2009.07.043

zbMATH Keywords

diameterplanar graphgraph orientationgraph minors

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20)

Related Items (10)

An Improvement to Chvátal and Thomassen’s Upper Bound for Oriented Diameter ⋮ Improved bounds for the oriented radius of mixed multigraphs ⋮ Bounds for the oriented diameter of planar triangulations ⋮ The complexity of two graph orientation problems ⋮ Series-parallel orientations preserving the cycle-radius ⋮ Route-enabling graph orientation problems ⋮ A degree condition for diameter two orientability of graphs ⋮ An improvement to Chvátal and Thomassen's upper bound for oriented diameter ⋮ Oriented diameter of star graphs ⋮ Location of speed-up subnetworks

Cites Work

• Graph minors. III. Planar tree-width
• Distances in orientations of graphs
• Quickly excluding a planar graph
• Diameter and treewidth in minor-closed graph families
• Bidimensional Parameters and Local Treewidth
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Minimizing the Oriented Diameter of a Planar Graph