Upward Point Set Embeddings of Paths and Trees

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10439120" target="_blank" >RIV/00216208:11320/21:10439120 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-030-68211-8_19" target="_blank" >https://doi.org/10.1007/978-3-030-68211-8_19</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-030-68211-8_19" target="_blank" >10.1007/978-3-030-68211-8_19</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Upward Point Set Embeddings of Paths and Trees

Popis výsledku v původním jazyce

We study upward planar straight-line embeddings (UPSE) of directed trees on given point sets. The given point set S has size at least the number of vertices in the tree. For the special case where the tree is a path P we show that: (a) If S is one-sided convex, the number of UPSE s equals the number of maximal monotone paths in P. (b) If S is in general position and P is composed by three maximal monotone paths, where the middle path is longer than the other two, then it always admits an UPSE on S. We show that the decision problem of whether there exists an UPSE of a directed tree with n vertices on a fixed point set S of n points is NP-complete, by relaxing the requirements of the previously known result which relied on the presence of cycles in the graph, but instead fixing position of a single vertex. Finally, by allowing extra points, we guarantee that each directed caterpillar on n vertices and with k switches in its backbone admits an UPSE on every set of n2k - 2 points.

Název v anglickém jazyce

Upward Point Set Embeddings of Paths and Trees

Popis výsledku anglicky

We study upward planar straight-line embeddings (UPSE) of directed trees on given point sets. The given point set S has size at least the number of vertices in the tree. For the special case where the tree is a path P we show that: (a) If S is one-sided convex, the number of UPSE s equals the number of maximal monotone paths in P. (b) If S is in general position and P is composed by three maximal monotone paths, where the middle path is longer than the other two, then it always admits an UPSE on S. We show that the decision problem of whether there exists an UPSE of a directed tree with n vertices on a fixed point set S of n points is NP-complete, by relaxing the requirements of the previously known result which relied on the presence of cycles in the graph, but instead fixing position of a single vertex. Finally, by allowing extra points, we guarantee that each directed caterpillar on n vertices and with k switches in its backbone admits an UPSE on every set of n2k - 2 points.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

WALCOM: Algorithms and Computation

ISBN

978-3-030-68210-1

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

13

Strana od-do

234-246

Název nakladatele

Springer Science and Business Media Deutschland GmbH

Místo vydání

Neuveden

Místo konání akce

MM

Datum konání akce

28. 2. 2021

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—