On Embeddability of Unit Disk Graphs onto Straight Lines

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F20%3A00114293" target="_blank" >RIV/00216224:14330/20:00114293 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-030-50026-9_13" target="_blank" >http://dx.doi.org/10.1007/978-3-030-50026-9_13</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-030-50026-9_13" target="_blank" >10.1007/978-3-030-50026-9_13</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On Embeddability of Unit Disk Graphs onto Straight Lines

Popis výsledku v původním jazyce

Unit disk graphs are the intersection graphs of unit radius disks in the Euclidean plane. Deciding whether there exists an embedding of a given unit disk graph, i.e., unit disk graph recognition, is an important geometric problem, and has many application areas. In general, this problem is known to be exists{}R-complete. In some applications, the objects that correspond to unit disks have predefined (geometrical) structures to be placed on. Hence, many researchers attacked this problem by restricting the domain of the disk centers. One example to such applications is wireless sensor networks, where each disk corresponds to a wireless sensor node, and a pair of intersecting disks corresponds to a pair of sensors being able to communicate with one another. It is usually assumed that the nodes have identical sensing ranges, and thus a unit disk graph model is used to model problems concerning wireless sensor networks. We consider the unit disk graph realization problem on a restricted domain, by assuming a scenario where the wireless sensor nodes are deployed on the corridors of a building. Based on this scenario, we impose a geometric constraint such that the unit disks must be centered onto given straight lines. In this paper, we first describe a polynomial-time reduction which shows that deciding whether a graph can be realized as unit disks onto given straight lines is NP-hard, when the given lines are parallel to either the x-axis or y-axis. Using the reduction we described, we also show that this problem is NP-complete when the given lines are only parallel to the x-axis (and one another). We obtain these results using the idea of the logic engine introduced by Bhatt and Cosmadakis in 1987

Název v anglickém jazyce

On Embeddability of Unit Disk Graphs onto Straight Lines

Popis výsledku anglicky

Unit disk graphs are the intersection graphs of unit radius disks in the Euclidean plane. Deciding whether there exists an embedding of a given unit disk graph, i.e., unit disk graph recognition, is an important geometric problem, and has many application areas. In general, this problem is known to be exists{}R-complete. In some applications, the objects that correspond to unit disks have predefined (geometrical) structures to be placed on. Hence, many researchers attacked this problem by restricting the domain of the disk centers. One example to such applications is wireless sensor networks, where each disk corresponds to a wireless sensor node, and a pair of intersecting disks corresponds to a pair of sensors being able to communicate with one another. It is usually assumed that the nodes have identical sensing ranges, and thus a unit disk graph model is used to model problems concerning wireless sensor networks. We consider the unit disk graph realization problem on a restricted domain, by assuming a scenario where the wireless sensor nodes are deployed on the corridors of a building. Based on this scenario, we impose a geometric constraint such that the unit disks must be centered onto given straight lines. In this paper, we first describe a polynomial-time reduction which shows that deciding whether a graph can be realized as unit disks onto given straight lines is NP-hard, when the given lines are parallel to either the x-axis or y-axis. Using the reduction we described, we also show that this problem is NP-complete when the given lines are only parallel to the x-axis (and one another). We obtain these results using the idea of the logic engine introduced by Bhatt and Cosmadakis in 1987

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

<a href="/cs/project/GA20-04567S" target="_blank" >GA20-04567S: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2020

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

International Computer Science Symposium in Russia, CSR 2020

ISBN

9783030500252

ISSN

0302-9743

e-ISSN

0302-9743

Počet stran výsledku

14

Strana od-do

184-197

Název nakladatele

Springer, Cham

Místo vydání

Yekaterinburg, Russia

Místo konání akce

Yekaterinburg, Russia

Datum konání akce

1. 1. 2020

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

WRD - Celosvětová akce

Kód UT WoS článku

—