Strict Confluent Drawing
Files
Publication date
2016
Authors
Eppstein, David
Holten, Danny
Löffler, Maarten
Nöllenburg, Martin
Speckmann, Bettina
Verbeek, Kevin
Editors
Advisors
Supervisors
DOI
Document Type
Article
Metadata
Show full item recordCollections
License
Abstract
We define strict confluent drawing, a form of confluent drawing in which the existence of an edge is indicated by the presence of a smooth path through a system of arcs and junctions (without crossings), and in which such a path, if it exists, must be unique. We prove that it is NP-complete to determine whether a given graph has a strict confluent drawing but polynomial to determine whether it has an outerplanar strict confluent drawing with a fixed vertex ordering (a drawing within a disk, with the vertices placed in a given order on the boundary).
Keywords
CG, GRAPH, GD
Citation
Eppstein, D, Holten, D, Löffler, M, Nöllenburg, M, Speckmann, B & Verbeek, K 2016, 'Strict Confluent Drawing', Journal of Computational Geometry, vol. 7, no. 1, pp. 22-46. < http://jocg.org/v7n1p2 >