Minimizing the Oriented Diameter of a Planar Graph

DOI10.1016/j.endm.2009.07.043zbMath1273.05052MaRDI 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

diameter; planar graph; graph orientation; graph minors

Mathematics Subject Classification ID

05C10: Planar graphs; geometric and topological aspects of graph theory

05C12: Distance in graphs

05C20: Directed graphs (digraphs), tournaments

Related Items

An Improvement to Chvátal and Thomassen’s Upper Bound for Oriented Diameter, Oriented diameter of star graphs, 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, A degree condition for diameter two orientability of graphs, Route-enabling graph orientation problems, An improvement to Chvátal and Thomassen's upper bound for oriented diameter, 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