On Embeddability of Unit Disk Graphs onto Straight Lines

DOI10.1007/978-3-030-50026-9_13OpenAlexW3035805791MaRDI QIDQ5042239

Onur Çağırıcı

Publication date: 19 October 2022

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Sphere and dot product representations of graphs
• 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
• Integer realizations of disk and segment graphs
• Encyclopedia of Optimization
• 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
• The complexity of satisfiability problems

This page was built for publication: On Embeddability of Unit Disk Graphs onto Straight Lines