Non-crossing paths with geographic constraints

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)
3 Downloads (Pure)

Abstract

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.

Original languageEnglish
Title of host publicationGraph drawing and network visualization - 25th International Symposium, GD 2017, Revised Selected Papers
EditorsF. Frati, K.-L. Ma
Place of PublicationCham
PublisherSpringer
Pages454-461
Number of pages8
ISBN (Electronic)978-3-319-73915-1
ISBN (Print)978-3-319-73914-4
DOIs
Publication statusPublished - 2018
Event25th International Symposium on Graph Drawing and Network Visualization (GD 2017) - Boston, United States
Duration: 25 Sept 201727 Sept 2017
Conference number: 25
https://gd2017.ccis.northeastern.edu/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume10692
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference25th International Symposium on Graph Drawing and Network Visualization (GD 2017)
Abbreviated titleGD 2017
Country/TerritoryUnited States
CityBoston
Period25/09/1727/09/17
Internet address

Funding

(MINECO/FEDER) and Gen. Cat. DGR2014SGR46, and by MINECO’s Ramón y Cajal program. B.S. and K.V. are supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 639.023.208 and 639.021.541, respectively.

Fingerprint

Dive into the research topics of 'Non-crossing paths with geographic constraints'. Together they form a unique fingerprint.

Cite this