Strict Confluent Drawing

David Eppstein; Danny Holten; Maarten Löffler; Martin Nöllenburg; Bettina Speckmann; Kevin Verbeek

Strict Confluent Drawing

David Eppstein, Danny Holten, Maarten Löffler, Martin Nöllenburg, Bettina Speckmann, Kevin Verbeek

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

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	Proc. 21st International Symposium on Graph Drawing
Publication status	Published - 2013

Keywords

CG, GRAPH, GD

Cite this

@inproceedings{71b64ab44d774ebfb5269716f1f65cfc,

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

keywords = "CG, GRAPH, GD",

author = "David Eppstein and Danny Holten and Maarten L{\"o}ffler and Martin N{\"o}llenburg and Bettina Speckmann and Kevin Verbeek",

note = "ehlnsv-scd-13 (to appear)",

year = "2013",

language = "English",

booktitle = "Proc. 21st International Symposium on Graph Drawing",

}

TY - GEN

T1 - Strict Confluent Drawing

AU - Eppstein, David

AU - Holten, Danny

AU - Löffler, Maarten

AU - Nöllenburg, Martin

AU - Speckmann, Bettina

AU - Verbeek, Kevin

N1 - ehlnsv-scd-13 (to appear)

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

KW - CG, GRAPH, GD

M3 - Conference contribution

BT - Proc. 21st International Symposium on Graph Drawing

ER -

Strict Confluent Drawing

Abstract

Keywords

Fingerprint

Cite this