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

DOI10.1016/J.DAM.2014.08.014zbMATH Open1321.05167OpenAlexW2158683956MaRDI QIDQ499355FDOQ499355

Authors: Guilherme D. Da Fonseca, V. G. Pereira de Sá, Celina Miraglia Herrera de Figueiredo, R. 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

Recommendations

• Unit disk graphs
• Discretization orders for distance geometry problems
• On embeddability of unit disk graphs onto straight lines
• Fast recognition of planar non unit distance graphs
• Unit disk graph recognition is NP-hard

zbMATH Keywords

discretizationtrigraphdistance geometryunit 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)

Cites Work

• Unit disk graph recognition is NP-hard
• Efficient graph representations
• Euclidean Distance Geometry and Applications
• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• Solving systems of polynomial inequalities in subexponential time
• Simple heuristics for unit disk graphs
• Graph-Theoretic Concepts in Computer Science
• 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

Cited In (5)

• On the embedding of cone graphs in the line with distinct distances between neighbors
• Representing graphs by disks and balls (a survey of recognition-complexity results)
• On embeddability of unit disk graphs onto straight lines
• On forbidden induced subgraphs for unit disk graphs
• Preface

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

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