On embeddability of unit disk graphs onto straight lines

DOI10.1007/S00224-022-10110-YzbMATH Open1512.05297arXiv1811.09881OpenAlexW3012693387MaRDI QIDQ6038709FDOQ6038709

Authors: Onur Çağırıcı 

Publication date: 2 May 2023

Published in: Theory of Computing Systems (Search for Journal in Brave)

Abstract: 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 $existsmathbbR$-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 $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 $x$-axis (and one another). We obtain those results using the idea of the logic engine introduced by Bhatt and Cosmadakis in 1987.

Full work available at URL: https://arxiv.org/abs/1811.09881

Recommendations

• Unit disk graph recognition is NP-hard
• Unit disk graphs
• Good quality virtual realization of unit disk graphs
• On the recognition of unit disk graphs and the distance geometry problem with ranges
• Representing graphs by disks and balls (a survey of recognition-complexity results)

zbMATH Keywords

NP-completenessrecognitionunit disk graphrestricted domain

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unit disk graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Unit disk graph recognition is NP-hard
• On coloring unit disk graphs
• Hamilton Paths in Grid Graphs
• The complexity of satisfiability problems
• Interval graphs and interval orders
• Sphere and dot product representations of graphs
• Thin strip graphs
• Integer realizations of disk and segment graphs
• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• Algorithmic Aspects of Wireless Sensor Networks
• On the recognition of unit disk graphs and the distance geometry problem with ranges
• The complexity of minimizing wire lengths in VLSI layouts
• Title not available (Why is that?)
• QPTAS and subexponential algorithm for maximum clique on disk graphs
• Recognizing a DOG is hard, but not when it is thin and unit

Cited In (4)

• Good quality virtual realization of unit disk graphs
• On a straight-line embedding problem of graphs
• Straight line embeddings of cubic planar graphs with integer edge lengths
• On the recognition of unit disk graphs and the distance geometry problem with ranges

This page was built for publication: On embeddability of unit disk graphs onto straight lines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6038709)