Non-crossing paths with geographic constraints

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

2 Citaten (Scopus)


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.

Originele taal-2Engels
TitelGraph drawing and network visualization - 25th International Symposium, GD 2017, Revised Selected Papers
RedacteurenF. Frati, K.-L. Ma
Plaats van productieCham
Aantal pagina's8
ISBN van elektronische versie978-3-319-73915-1
ISBN van geprinte versie978-3-319-73914-4
StatusGepubliceerd - 2018
Evenement25th International Symposium on Graph Drawing and Network Visualization (GD 2017) - Boston, Verenigde Staten van Amerika
Duur: 25 sep 201727 sep 2017
Congresnummer: 25

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349


Congres25th International Symposium on Graph Drawing and Network Visualization (GD 2017)
Verkorte titelGD 2017
Land/RegioVerenigde Staten van Amerika
Internet adres


Duik in de onderzoeksthema's van 'Non-crossing paths with geographic constraints'. Samen vormen ze een unieke vingerafdruk.

Citeer dit