Non-crossing paths with geographic constraints

R.I. Silveira; B. Speckmann; K.A.B. Verbeek

doi:10.1007/978-3-319-73915-1_35

Non-crossing paths with geographic constraints

R.I. Silveira, B. Speckmann, K.A.B. Verbeek

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

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 language	English
Title of host publication	Graph drawing and network visualization - 25th International Symposium, GD 2017, Revised Selected Papers
Editors	F. Frati, K.-L. Ma
Place of Publication	Cham
Publisher	Springer
Pages	454-461
Number of pages	8
ISBN (Electronic)	978-3-319-73915-1
ISBN (Print)	978-3-319-73914-4
DOIs	https://doi.org/10.1007/978-3-319-73915-1_35
Publication status	Published - 2018
Event	25th International Symposium on Graph Drawing and Network Visualization (GD 2017) - Boston, United States Duration: 25 Sep 2017 → 27 Sep 2017 Conference number: 25 https://gd2017.ccis.northeastern.edu/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	10692
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	25th International Symposium on Graph Drawing and Network Visualization (GD 2017)
Abbreviated title	GD 2017
Country	United States
City	Boston
Period	25/09/17 → 27/09/17
Internet address	https://gd2017.ccis.northeastern.edu/

Access to Document

10.1007/978-3-319-73915-1_35

Link to publication in Scopus

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

Cite this

Silveira, R. I., Speckmann, B., & Verbeek, K. A. B. (2018). Non-crossing paths with geographic constraints. In F. Frati, & K-L. Ma (Eds.), Graph drawing and network visualization - 25th International Symposium, GD 2017, Revised Selected Papers (pp. 454-461). (Lecture Notes in Computer Science ; Vol. 10692). Springer. https://doi.org/10.1007/978-3-319-73915-1_35

@inproceedings{11065e2a86124825866e6801268c642d,

title = "Non-crossing paths with geographic constraints",

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.",

author = "R.I. Silveira and B. Speckmann and K.A.B. Verbeek",

year = "2018",

doi = "10.1007/978-3-319-73915-1_35",

language = "English",

isbn = "978-3-319-73914-4",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "454--461",

editor = "F. Frati and K.-L. Ma",

booktitle = "Graph drawing and network visualization - 25th International Symposium, GD 2017, Revised Selected Papers",

address = "Germany",

note = "25th International Symposium on Graph Drawing and Network Visualization (GD 2017), GD 2017 ; Conference date: 25-09-2017 Through 27-09-2017",

url = "https://gd2017.ccis.northeastern.edu/",

}

Silveira, RI, Speckmann, B & Verbeek, KAB 2018, Non-crossing paths with geographic constraints. in F Frati & K-L Ma (eds), Graph drawing and network visualization - 25th International Symposium, GD 2017, Revised Selected Papers. Lecture Notes in Computer Science , vol. 10692, Springer, Cham, pp. 454-461, 25th International Symposium on Graph Drawing and Network Visualization (GD 2017), Boston, United States, 25/09/17. https://doi.org/10.1007/978-3-319-73915-1_35

Non-crossing paths with geographic constraints. / Silveira, R.I.; Speckmann, B.; Verbeek, K.A.B.

Graph drawing and network visualization - 25th International Symposium, GD 2017, Revised Selected Papers. ed. / F. Frati; K.-L. Ma. Cham : Springer, 2018. p. 454-461 (Lecture Notes in Computer Science ; Vol. 10692).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Non-crossing paths with geographic constraints

AU - Silveira, R.I.

AU - Speckmann, B.

AU - Verbeek, K.A.B.

N1 - Conference code: 25

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85041862111&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-73915-1_35

DO - 10.1007/978-3-319-73915-1_35

M3 - Conference contribution

AN - SCOPUS:85041862111

SN - 978-3-319-73914-4

T3 - Lecture Notes in Computer Science

SP - 454

EP - 461

BT - Graph drawing and network visualization - 25th International Symposium, GD 2017, Revised Selected Papers

A2 - Frati, F.

A2 - Ma, K.-L.

PB - Springer

CY - Cham

T2 - 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)

Y2 - 25 September 2017 through 27 September 2017

ER -