Shortest directed networks in the plane

DOI10.1007/S00373-020-02183-8zbMATH Open1458.05093arXiv1903.07172OpenAlexW3034301632MaRDI QIDQ2227985FDOQ2227985

Konrad J. Swanepoel, Alastair Maxwell

Publication date: 16 February 2021

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: Given a set of sources and a set of sinks as points in the Euclidean plane, a directed network is a directed graph drawn in the plane with a directed path from each source to each sink. Such a network may contain nodes other than the given sources and sinks, called Steiner points. We characterize the local structure of the Steiner points in all shortest-length directed networks in the Euclidean plane. This characterization implies that these networks are constructible by straightedge and compass. Our results build on unpublished work of Alfaro, Campbell, Sher, and Soto from 1989 and 1990. Part of the proof is based on a new method that uses other norms in the plane. This approach gives more conceptual proofs of some of their results, and as a consequence, we also obtain results on shortest directed networks for these norms.

Full work available at URL: https://arxiv.org/abs/1903.07172

zbMATH Keywords

normed planestraightedge and compassEuclidean Steiner problemshortest directed network

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Deterministic network models in operations research (90B10) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Planar graphs; geometric and topological aspects of graph theory (05C10) Optimization of shapes other than minimal surfaces (49Q10) Inequalities and extremum problems involving convexity in convex geometry (52A40)

Cites Work

• Steiner Minimal Trees
• The local Steiner problem in normed planes
• Existence of shortest directed networks in \(\mathbb{R}^ 2\)
• On the existence of shortest directed networks
• Title not available (Why is that?)
• Optimal interconnection trees in the plane. Theory, algorithms and applications
• On the history of the Euclidean Steiner tree problem

Cited In (4)

• Existence of shortest directed networks in \(\mathbb{R}^ 2\)
• Structural properties of minimum multi-source multi-sink Steiner networks in the Euclidean plane
• Locally minimal uniformly oriented shortest networks
• On the existence of shortest directed networks

   Recommendations

• On the existence of shortest directed networks 👍 👎
• Determining shortest networks in the Euclidean plane 👍 👎
• Title not available (Why is that?) 👍 👎
• The shortest network under a given topology 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Existence of shortest directed networks in \(\mathbb{R}^ 2\) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Shortest directed networks in the plane

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