Shortest directed networks in the plane

Maxwell, Alastair and Swanepoel, Konrad (2020) Shortest directed networks in the plane. Graphs and Combinatorics, 36 (5). 1457 - 1475. ISSN 0911-0119

Text (Shortest directed networks in the place) - Published Version Available under License Creative Commons Attribution. Download (737kB)

• Author

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 charac- terization implies that these networks are constructible by straightedge and compass. Our results build on unpublished work of Alfaro, Camp- bell, 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.

Item Type:	Article
Official URL:	https://www.springer.com/journal/373
Additional Information:	© 2020 The Authors
Divisions:	Mathematics
Subjects:	Q Science > QA Mathematics
Date Deposited:	13 May 2020 10:33
Last Modified:	20 Sep 2025 01:51
URI:	http://eprintstest.lse.ac.uk/id/eprint/104368

Actions (login required)

View Item