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).
Original language | English |
---|---|
Title of host publication | Graph Drawing (21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013. Revised Selected Papers) |
Editors | S. Wismath, A. Wolff |
Place of Publication | Cham |
Publisher | Springer |
Pages | 352-363 |
ISBN (Print) | 978-3-319-03840-7 |
DOIs | |
Publication status | Published - 2013 |
Event | 21st International Symposium on Graph Drawing (GD 2013) - Bordeaux, France Duration: 23 Sept 2013 → 25 Sept 2013 Conference number: 21 http://gd2013.labri.fr/ |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Volume | 8242 |
ISSN (Print) | 0302-9743 |
Conference
Conference | 21st International Symposium on Graph Drawing (GD 2013) |
---|---|
Abbreviated title | GD 2013 |
Country/Territory | France |
City | Bordeaux |
Period | 23/09/13 → 25/09/13 |
Other | 21st International Symposium on Graph Drawing |
Internet address |