On embeddability of unit disk graphs onto straight lines

DOI10.1007/s00224-022-10110-yzbMath1512.05297arXiv1811.09881OpenAlexW3012693387MaRDI QIDQ6038709

Onur Çağırıcı

Publication date: 2 May 2023

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

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

zbMATH Keywords

NP-completenessrecognitionunit disk graphrestricted domain

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Thin strip graphs
• Sphere and dot product representations of graphs
• On the recognition of unit disk graphs and the distance geometry problem with ranges
• Interval graphs and interval orders
• The complexity of minimizing wire lengths in VLSI layouts
• 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
• Integer realizations of disk and segment graphs
• Hamilton Paths in Grid Graphs
• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• Recognizing a DOG is Hard but not when it is Thin and Unit
• Algorithmic Aspects of Wireless Sensor Networks
• The complexity of satisfiability problems

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