Noncrossing Paths with Geographic ConstraintsSilveira, Rodrigo I. and Speckmann, Bettina and Verbeek, Kevin (2017) Noncrossing Paths with Geographic Constraints. In: Graph Drawing and Network Visualization. GD 2017, September 2527 , pp. 454464(Official URL: https://doi.org/10.1007/9783319739151_35). Full text not available from this repository.
Official URL: https://doi.org/10.1007/9783319739151_35
AbstractA 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 NPcomplete to determine if a crossingfree 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.
Actions (login required)
