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

DOI10.1016/J.DAM.2014.08.014MaRDI QIDQ499355zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• Efficient graph representations
• Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
• Euclidean distance geometry and applications
• Graph-Theoretic Concepts in Computer Science
• Integer realizations of disk and segment graphs
• Linear time approximation for dominating sets and independent dominating sets in unit disk graphs
• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• Simple heuristics for unit disk graphs
• Solving systems of polynomial inequalities in subexponential time
• Unit disk graph recognition is NP-hard

Cited in

(6)

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

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)