Non-Crossing Geometric Steiner Arborescences

Kostitsyna, Irina; Speckmann, Bettina; Verbeek, Kevin

doi:10.4230/LIPIcs.ISAAC.2017.54

File

LIPIcs.ISAAC.2017.54.pdf

Filesize: 0.99 MB
13 pages

Document Identifiers

DOI: 10.4230/LIPIcs.ISAAC.2017.54
URN: urn:nbn:de:0030-drops-82342

Author Details

Irina Kostitsyna

Bettina Speckmann

Kevin Verbeek

Cite AsGet BibTex

Irina Kostitsyna, Bettina Speckmann, and Kevin Verbeek. Non-Crossing Geometric Steiner Arborescences. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 54:1-54:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ISAAC.2017.54

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.

Keywords

Steiner arborescences
non-crossing drawing
rectilinear
angle-restricted

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

Oswin Aichholzer, Franz Aurenhammer, Thomas Hackl, and Clemens Huemer. Connecting colored point sets. Discrete Applied Mathematics, 155(3):271-278, 2007. URL: http://dx.doi.org/10.1016/j.dam.2006.06.010.
Oswin Aichholzer, Franz Aurenhammer, Christian Icking, Rolf Klein, Elmar Langetepe, and Günter Rote. Generalized self-approaching curves. Discrete Applied Mathematics, 109(1-2):3-24, apr 2001. URL: http://dx.doi.org/10.1016/S0166-218X(00)00233-X.
Sanjeev Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM, 45(5):753-782, 1998.
Sergey Bereg, Krzysztof Fleszar, Philipp Kindermann, Sergey Pupyrev, Joachim Spoerhase, and Alexander Wolff. Colored non-crossing Euclidean Steiner forest. In Proc. 26th International Symposium on Algorithms and Computation (ISAAC), pages 429-441, 2015. URL: http://arxiv.org/abs/1509.05681.
Kevin Buchin, Bettina Speckmann, and Kevin Verbeek. Angle-restricted Steiner arborescences for flow map layout. Algorithmica, 72(2):656-685, 2015. URL: http://dx.doi.org/10.1007/s00453-013-9867-z.
Klaus Jansen and Gerhard J. Woeginger. The complexity of detecting crossingfree configurations in the plane. BIT Numerical Mathematics, 33(4):580-595, 1993. URL: http://dx.doi.org/10.1007/BF01990536.
M. Kano, C. Merino, and J. Urrutia. On plane spanning trees and cycles of multicolored point sets with few intersections. Information Processing Letters, 93(6):301-306, 2005.
Christian Knauer, Étienne Schramm, Andreas Spillner, and Alexander Wolff. Configurations with few crossings in topological graphs. Computational Geometry, 37(2):104-114, 2007. URL: http://dx.doi.org/10.1016/j.comgeo.2006.06.001.
J. Leaños, C. Merino, G. Salazar, and J. Urrutia. Spanning trees of multicoloured point sets with few intersections. In Proc. Indonesia-Japan Joint Conference on Combinatorial Geometry and Graph Theory (IJCCGGT), LNCS 3330, pages 113-122, 2005.
Bing Lu and Lu Ruan. Polynomial time approximation scheme for the rectilinear Steiner arborescence problem. Journal of Combinatorial Optimization, 4(3):357-363, 2000. URL: http://dx.doi.org/10.1023/A:1009826311973.
Julia Schüler and Andreas Spillner. Crossing-free spanning trees in visibility graphs of points between monotone polygonal obstacles. In Proc. 9th International Computer Science Symposium in Russia (CSR), LNCS 8476, pages 337-350, 2014.
Shin-ichi Tokunaga. Intersection number of two connected geometric graphs. Information Processing Letters, 59(6):331-333, 1996. URL: http://dx.doi.org/10.1016/0020-0190(96)00124-X.