Non-crossing geometric steiner arborescences

I. Kostitsyna; B. Speckmann; K.A.B. Verbeek

doi:10.4230/LIPIcs.ISAAC.2017.54

Non-crossing geometric steiner arborescences

I. Kostitsyna, B. Speckmann, K.A.B. Verbeek

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

184 Downloads (Pure)

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.

Original language	English
Title of host publication	28th International Symposium on Algorithms and Computation, ISAAC 2017
Editors	Yoshio Okamoto, Takeshi Tokuyama
Place of Publication	Dagstuhl
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	1-13
ISBN (Electronic)	9783959770545
ISBN (Print)	978-3-95977-054-5
DOIs	https://doi.org/10.4230/LIPIcs.ISAAC.2017.54
Publication status	Published - 2017
Event	28th International Symposium on Algorithms and Computation (ISAAC 2017) - Phuket, Thailand Duration: 9 Dec 2017 → 12 Dec 2017 Conference number: 28 http://aiat.in.th/isaac2017/

Publication series

Name	Leibniz International Proceedings in Informatics (LIPIcs)
Publisher	Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Volume	92

Conference

Conference	28th International Symposium on Algorithms and Computation (ISAAC 2017)
Abbreviated title	ISAAC 2017
Country/Territory	Thailand
City	Phuket
Period	9/12/17 → 12/12/17
Internet address	http://aiat.in.th/isaac2017/

Keywords

Angle-restricted
Non-crossing drawing
Rectilinear
Steiner arborescences

Access to Document

10.4230/LIPIcs.ISAAC.2017.54

publishers versionFinal published version, 0.99 MBLicence: CC BY

Cite this

Kostitsyna, I., Speckmann, B., & Verbeek, K. A. B. (2017). Non-crossing geometric steiner arborescences. In Y. Okamoto, & T. Tokuyama (Eds.), 28th International Symposium on Algorithms and Computation, ISAAC 2017 (pp. 1-13). Article 54 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 92). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ISAAC.2017.54

@inproceedings{da28f110765046eb90ff641ce0c77c86,

title = "Non-crossing geometric steiner arborescences",

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 = "Angle-restricted, Non-crossing drawing, Rectilinear, Steiner arborescences",

author = "I. Kostitsyna and B. Speckmann and K.A.B. Verbeek",

year = "2017",

doi = "10.4230/LIPIcs.ISAAC.2017.54",

language = "English",

isbn = "978-3-95977-054-5",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "1--13",

editor = "Yoshio Okamoto and Takeshi Tokuyama",

booktitle = "28th International Symposium on Algorithms and Computation, ISAAC 2017",

note = "28th International Symposium on Algorithms and Computation (ISAAC 2017), ISAAC 2017 ; Conference date: 09-12-2017 Through 12-12-2017",

url = "http://aiat.in.th/isaac2017/",

}

Kostitsyna, I, Speckmann, B & Verbeek, KAB 2017, Non-crossing geometric steiner arborescences. in Y Okamoto & T Tokuyama (eds), 28th International Symposium on Algorithms and Computation, ISAAC 2017., 54, Leibniz International Proceedings in Informatics (LIPIcs), vol. 92, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, pp. 1-13, 28th International Symposium on Algorithms and Computation (ISAAC 2017), Phuket, Thailand, 9/12/17. https://doi.org/10.4230/LIPIcs.ISAAC.2017.54

Non-crossing geometric steiner arborescences. / Kostitsyna, I.; Speckmann, B.; Verbeek, K.A.B.
28th International Symposium on Algorithms and Computation, ISAAC 2017. ed. / Yoshio Okamoto; Takeshi Tokuyama. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. p. 1-13 54 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 92).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Non-crossing geometric steiner arborescences

AU - Kostitsyna, I.

AU - Speckmann, B.

AU - Verbeek, K.A.B.

N1 - Conference code: 28

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - Angle-restricted

KW - Non-crossing drawing

KW - Rectilinear

KW - Steiner arborescences

UR - http://www.scopus.com/inward/record.url?scp=85038598499&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ISAAC.2017.54

DO - 10.4230/LIPIcs.ISAAC.2017.54

M3 - Conference contribution

SN - 978-3-95977-054-5

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 1

EP - 13

BT - 28th International Symposium on Algorithms and Computation, ISAAC 2017

A2 - Okamoto, Yoshio

A2 - Tokuyama, Takeshi

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

CY - Dagstuhl

T2 - 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Y2 - 9 December 2017 through 12 December 2017

ER -

Non-crossing geometric steiner arborescences

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this