• Non-crossing paths with geogra...

Treffer: Non-crossing paths with geographic constraints

Title:
Non-crossing paths with geographic constraints
Authors:
Silveira, Rodrigo Ignacio, Speckmann, Bettina, Verbeek, Kevin
Contributors:
Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. CGA - Computational Geometry and Applications
Publisher Information:
Chapman & Hall/CRC
Publication Year:
2019
Collection:
Universitat Politècnica de Catalunya, BarcelonaTech: UPCommons - Global access to UPC knowledge
Subject Terms:
Àrees temàtiques de la UPC::Matemàtiques i estadística::Anàlisi numèrica::Mètodes numèrics, Numerical analysis, non-crossing connectors problem, constrained graph drawing, Anàlisi numèrica, Classificació AMS::65 Numerical analysis::65D Numerical approximation and computational geometry
Document Type:
Fachzeitschrift article in journal/newspaper
File Description:
8 p.; application/pdf
Language:
English
Relation:
https://link.springer.com/chapter/10.1007/978-3-319-73915-1_35; info:eu-repo/grantAgreement/MINECO//MTM2015-63791-R/ES/GRAFOS Y GEOMETRIA: INTERACCIONES Y APLICACIONES/; https://arxiv.org/pdf/1708.05486.pdf; http://hdl.handle.net/2117/174889
DOI:
10.1007/978-3-319-73915-1_35
Availability:
http://hdl.handle.net/2117/174889
https://arxiv.org/pdf/1708.05486.pdf
https://doi.org/10.1007/978-3-319-73915-1_35
Rights:
Open Access
Accession Number:
edsbas.1B4A7816
Database:
BASE

Weitere Informationen

A geographic network is a graph whose vertices are restricted to lie in a prescribed region in the plane. In this paper we begin to study the following fundamental problem for geographic networks: can a given geographic network be drawn without crossings? We focus on the seemingly simple setting where each region is a unit length vertical segment, and one wants to connect pairs of segments with a path that lies inside the convex hull of the two segments. We prove that when paths must be drawn as straight line segments, it is NP-complete to determine if a crossing-free solution exists. In contrast, we show that when paths must be monotone curves, the question can be answered in polynomial time. In the more general case of paths that can have any shape, we show that the problem is polynomial under certain assumptions. ; Peer Reviewed ; Postprint (author's final draft)