2026-07-21T03:14:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8234 2024-03-06T10:41:52Z ddc:004 open_access

Non-Crossing Geometric Steiner Arborescences Kostitsyna, Irina Speckmann, Bettina Verbeek, Kevin Steiner arborescences non-crossing drawing rectilinear angle-restricted Motivated by the question of simultaneous embedding of several flow maps, we consider the problem of drawing multiple geometric Steiner arborescences with no crossings in the rectilinear and in the angle-restricted setting. When terminal-to-root paths are allowed to turn freely, we show that two rectilinear Steiner arborescences have a non-crossing drawing if neither tree necessarily completely disconnects the other tree and if the roots of both trees are "free". If the roots are not free, then we can reduce the decision problem to 2SAT. If terminal-to-root paths are allowed to turn only at Steiner points, then it is NP-hard to decide whether multiple rectilinear Steiner arborescences have a non-crossing drawing. The setting of angle-restricted Steiner arborescences is more subtle than the rectilinear case. Our NP-hardness result extends, but testing whether there exists a non-crossing drawing if the roots of both trees are free requires additional conditions to be fulfilled. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Irina Kostitsyna and Bettina Speckmann and Kevin Verbeek 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.54 urn:nbn:de:0030-drops-82342 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.54 eng https://creativecommons.org/licenses/by/3.0/legalcode