On the recognition of unit disk graphs and the distance geometry problem with ranges

DOI10.1016/j.dam.2014.08.014zbMath1321.05167OpenAlexW2158683956MaRDI QIDQ499355

Vinícius Gusmão Pereira de Sá, Guilherme Dias da Fonseca, Celina Miraglia Herrera de Figueiredo, Raphael C. S. Machado

Publication date: 30 September 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2014.08.014

zbMATH Keywords

discretizationdistance geometrytrigraphunit disk graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (4)

On embeddability of unit disk graphs onto straight lines ⋮ On the embedding of cone graphs in the line with distinct distances between neighbors ⋮ On forbidden induced subgraphs for unit disk graphs ⋮ Preface

Cites Work

• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• Solving systems of polynomial inequalities in subexponential time
• Unit disk graph recognition is NP-hard
• Efficient graph representations
• Integer realizations of disk and segment graphs
• Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
• Linear Time Approximation for Dominating Sets and Independent Dominating Sets in Unit Disk Graphs
• Simple heuristics for unit disk graphs
• Euclidean Distance Geometry and Applications
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: On the recognition of unit disk graphs and the distance geometry problem with ranges