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 proceedingConference contributionAcademicpeer-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 languageEnglish
Title of host publicationGraph Drawing (21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013. Revised Selected Papers)
EditorsS. Wismath, A. Wolff
Place of PublicationCham
PublisherSpringer
Pages352-363
ISBN (Print)978-3-319-03840-7
DOIs
Publication statusPublished - 2013
Event21st International Symposium on Graph Drawing (GD 2013) - Bordeaux, France
Duration: 23 Sept 201325 Sept 2013
Conference number: 21
http://gd2013.labri.fr/

Publication series

NameLecture Notes in Computer Science
Volume8242
ISSN (Print)0302-9743

Conference

Conference21st International Symposium on Graph Drawing (GD 2013)
Abbreviated titleGD 2013
Country/TerritoryFrance
CityBordeaux
Period23/09/1325/09/13
Other21st International Symposium on Graph Drawing
Internet address

Fingerprint

Dive into the research topics of 'Strict confluent drawing'. Together they form a unique fingerprint.

Cite this