Strongly connected orientations of plane graphs

DOI10.1016/J.DAM.2012.08.004MaRDI QIDQ1759876zbMATH OpenOpenAlexFDO

Authors Evangelos Kranakis, Oscar Morales, Ladislav Stacho

Publication date 22 November 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2012.08.004

zbMATH Keywords

cut edgesdigraphdirectional antennaeedge orientationnumber of oriented arcsplane graphsensorsspannerstretch factorstrongly connected subgraps

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Review text

The purpose of the paper is to orient a subset of edges of a given plane graph such that the resulting subgraph is strongly connected and spans all vertices of the graph. In addition, the number of oriented arcs is minimum and at the same time produces a digraph with smallest possible stretch factor. The paper also presents three constructions for such orientations.

Recommendations

• Strong orientations of planar graphs with bounded stretch factor
• Strongly 2-connected orientations of graphs
• On the Optimal Strongly Connected Orientations of City Street Graphs I: Large Grids
• Strongly connected orientations of mixed multigraphs
• Parallel strong orientation on a mesh connected computer

Cited in

(5)

• Planar orientations with low out-degree and compaction of adjacency matrices
• Cell rotation graphs of strongly connected orientations of plane graphs with an application
• The flow index and strongly connected orientations
• Strong orientations of planar graphs with bounded stretch factor
• On the Structure of the Strong Orientations of a Graph

This page was built for publication: Strongly connected orientations of plane graphs

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