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: Contribution to journal › Article › 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
Pages (from-to)	22-46
Number of pages	25
Journal	Journal of Computational Geometry
Volume	7
Issue number	1
Publication status	Published - 2016

Keywords

CG
GRAPH
GD

Access to Document

STRICTFinal published version, 1.55 MB

http://jocg.org/v7n1p2

Cite this

@article{0a18746e9b4344b4879c696998ab83dd,

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

year = "2016",

language = "English",

volume = "7",

pages = "22--46",

journal = "Journal of Computational Geometry",

issn = "1920-180X",

publisher = "Carleton University",

number = "1",

}

TY - JOUR

T1 - Strict Confluent Drawing

AU - Eppstein, David

AU - Holten, Danny

AU - Löffler, Maarten

AU - Nöllenburg, Martin

AU - Speckmann, Bettina

AU - Verbeek, Kevin

PY - 2016

Y1 - 2016

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

KW - GRAPH

KW - GD

M3 - Article

SN - 1920-180X

VL - 7

SP - 22

EP - 46

JO - Journal of Computational Geometry

JF - Journal of Computational Geometry

IS - 1

ER -

Strict Confluent Drawing

Abstract

Keywords

Access to Document

Fingerprint

Cite this