Strict confluent drawing

D. Eppstein; D.H.R. Holten; M. Löffler; M. Nöllenburg; B. Speckmann; K.A.B. Verbeek

doi:10.1007/978-3-319-03841-4_31

Strict confluent drawing

D. Eppstein, D.H.R. Holten, M. Löffler, M. Nöllenburg, B. Speckmann, K.A.B. Verbeek

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

6 Citations (Scopus)

3 Downloads (Pure)

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	https://doi.org/10.1007/978-3-319-03841-4_31
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	http://gd2013.labri.fr/

Access to Document

10.1007/978-3-319-03841-4_31

Cite this

Eppstein, D., Holten, D. H. R., Löffler, M., Nöllenburg, M., Speckmann, B., & Verbeek, K. A. B. (2013). Strict confluent drawing. In S. Wismath, & A. Wolff (Eds.), Graph Drawing (21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013. Revised Selected Papers) (pp. 352-363). (Lecture Notes in Computer Science; Vol. 8242). Springer. https://doi.org/10.1007/978-3-319-03841-4_31

@inproceedings{3c2c2cf7ee93405294c671aac9871b3e,

title = "Strict confluent drawing",

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

author = "D. Eppstein and D.H.R. Holten and M. L{\"o}ffler and M. N{\"o}llenburg and B. Speckmann and K.A.B. Verbeek",

year = "2013",

doi = "10.1007/978-3-319-03841-4_31",

language = "English",

isbn = "978-3-319-03840-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "352--363",

editor = "S. Wismath and A. Wolff",

booktitle = "Graph Drawing (21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013. Revised Selected Papers)",

address = "Germany",

note = "21st International Symposium on Graph Drawing (GD 2013), GD 2013 ; Conference date: 23-09-2013 Through 25-09-2013",

url = "http://gd2013.labri.fr/",

}

Eppstein, D, Holten, DHR, Löffler, M, Nöllenburg, M, Speckmann, B & Verbeek, KAB 2013, Strict confluent drawing. in S Wismath & A Wolff (eds), Graph Drawing (21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013. Revised Selected Papers). Lecture Notes in Computer Science, vol. 8242, Springer, Cham, pp. 352-363, 21st International Symposium on Graph Drawing (GD 2013), Bordeaux, France, 23/09/13. https://doi.org/10.1007/978-3-319-03841-4_31

Strict confluent drawing. / Eppstein, D.; Holten, D.H.R.; Löffler, M. et al.
Graph Drawing (21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013. Revised Selected Papers). ed. / S. Wismath; A. Wolff. Cham: Springer, 2013. p. 352-363 (Lecture Notes in Computer Science; Vol. 8242).

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

TY - GEN

T1 - Strict confluent drawing

AU - Eppstein, D.

AU - Holten, D.H.R.

AU - Löffler, M.

AU - Nöllenburg, M.

AU - Speckmann, B.

AU - Verbeek, K.A.B.

N1 - Conference code: 21

PY - 2013

Y1 - 2013

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

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

U2 - 10.1007/978-3-319-03841-4_31

DO - 10.1007/978-3-319-03841-4_31

M3 - Conference contribution

SN - 978-3-319-03840-7

T3 - Lecture Notes in Computer Science

SP - 352

EP - 363

BT - Graph Drawing (21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013. Revised Selected Papers)

A2 - Wismath, S.

A2 - Wolff, A.

PB - Springer

CY - Cham

T2 - 21st International Symposium on Graph Drawing (GD 2013)

Y2 - 23 September 2013 through 25 September 2013

ER -

Strict confluent drawing

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this