Strict Confluent Drawing

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

    Research output: Contribution to journalArticleAcademicpeer-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 languageEnglish
    Pages (from-to)22-46
    Number of pages25
    JournalJournal of Computational Geometry
    Volume7
    Issue number1
    Publication statusPublished - 2016

    Keywords

    • CG
    • GRAPH
    • GD

    Fingerprint

    Dive into the research topics of 'Strict Confluent Drawing'. Together they form a unique fingerprint.

    Cite this