License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2017.54
URN: urn:nbn:de:0030-drops-82342
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8234/
Go to the corresponding LIPIcs Volume Portal

Kostitsyna, Irina ; Speckmann, Bettina ; Verbeek, Kevin

Non-Crossing Geometric Steiner Arborescences

pdf-format:
LIPIcs-ISAAC-2017-54.pdf (1.0 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{kostitsyna_et_al:LIPIcs:2017:8234,
  author =	{Irina Kostitsyna and Bettina Speckmann and Kevin Verbeek},
  title =	{{Non-Crossing Geometric Steiner Arborescences}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{54:1--54:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Yoshio Okamoto and Takeshi Tokuyama},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8234},
  URN =		{urn:nbn:de:0030-drops-82342},
  doi =		{10.4230/LIPIcs.ISAAC.2017.54},
  annote =	{Keywords: Steiner arborescences, non-crossing drawing, rectilinear, angle-restricted}
}

Keywords: Steiner arborescences, non-crossing drawing, rectilinear, angle-restricted
Collection: 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Issue Date: 2017
Date of publication: 07.12.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI