Geodesic
Non-crossing paths with geographic constraints
Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 3.

Voir la notice de l'article provenant de la source Episciences

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 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, even if all vertical segments have unit length. 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. 
@article{DMTCS_2019_21_3_a14,
     author = {Silveira, Rodrigo I. and Speckmann, Bettina and Verbeek, Kevin},
     title = {Non-crossing paths with geographic constraints},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {21},
     number = {3},
     year = {2019},
     doi = {10.23638/DMTCS-21-3-15},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-15/}
}
TY  - JOUR
AU  - Silveira, Rodrigo I.
AU  - Speckmann, Bettina
AU  - Verbeek, Kevin
TI  - Non-crossing paths with geographic constraints
JO  - Discrete mathematics & theoretical computer science
PY  - 2019
VL  - 21
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-15/
DO  - 10.23638/DMTCS-21-3-15
LA  - en
ID  - DMTCS_2019_21_3_a14
ER  - 
%0 Journal Article
%A Silveira, Rodrigo I.
%A Speckmann, Bettina
%A Verbeek, Kevin
%T Non-crossing paths with geographic constraints
%J Discrete mathematics & theoretical computer science
%D 2019
%V 21
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-15/
%R 10.23638/DMTCS-21-3-15
%G en
%F DMTCS_2019_21_3_a14
Silveira, Rodrigo I.; Speckmann, Bettina; Verbeek, Kevin. Non-crossing paths with geographic constraints. Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 3. doi : 10.23638/DMTCS-21-3-15. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-15/

Cité par Sources :