Rodrigo I. Silveira ; Bettina Speckmann ; Kevin Verbeek - Non-crossing paths with geographic constraints

dmtcs:4334 - Discrete Mathematics & Theoretical Computer Science, May 23, 2019, Vol. 21 no. 3 - https://doi.org/10.23638/DMTCS-21-3-15
Non-crossing paths with geographic constraintsArticle

Authors: Rodrigo I. Silveira ; Bettina Speckmann ; Kevin Verbeek

    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.


    Volume: Vol. 21 no. 3
    Section: Discrete Algorithms
    Published on: May 23, 2019
    Accepted on: April 23, 2019
    Submitted on: March 1, 2018
    Keywords: Computer Science - Computational Geometry
    Funding:
      Source : OpenAIRE Graph
    • Stable Geometric Algorithms; Funder: Netherlands Organisation for Scientific Research (NWO); Code: 639.021.541
    • Algorithmic Foundations for the Analysis and Visualization of Complex Moving Objects; Funder: Netherlands Organisation for Scientific Research (NWO); Code: 639.023.208

    2 Documents citing this article

    Consultation statistics

    This page has been seen 766 times.
    This article's PDF has been downloaded 291 times.