Book chapter
Good Quality Virtual Realization of Unit Ball Graphs
Algorithms – ESA 2007, pp.311-322
Lecture Notes in Computer Science, Springer Berlin Heidelberg
2007
DOI: 10.1007/978-3-540-75520-3_29
Abstract
The quality of an embedding Φ: V ↦ℝ2 of a graph G = (V, E) into the Euclidean plane is the ratio of max {u, v} ∈ E ||Φ(u) − Φ(v)||2 to \documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\min_{\{u, v\} \not\in E} ||\Phi(u) - \Phi(v)||_2$\end{document}. Given a unit disk graph G = (V, E), we seek algorithms to compute an embedding Φ: V ↦ℝ2 of best (smallest) quality. This paper presents a simple, combinatorial algorithm for computing a O(log2.5n)-quality 2-dimensional embedding of a given unit disk graph. Note that G comes with no associated geometric information. If the embedding is allowed to reside in higher dimensional space, we obtain improved results: a quality-2 embedding in ℝO(1). Our results extend to unit ball graphs (UBGs) in fixed dimensional Euclidean space. Constructing a “growth-restricted approximation” of the given unit disk graph lies at the core of our algorithm. This approach allows us to bypass the standard and costly technique of solving a linear program with exponentially many “spreading constraints.” As a side effect of our construction, we get a constant-factor approximation to the minimum clique cover problem on UBGs, described without geometry. Our problem is a version of the well known localization problem in wireless networks.
Details
- Title: Subtitle
- Good Quality Virtual Realization of Unit Ball Graphs
- Creators
- Sriram V. Pemmaraju - University of IowaImran A. Pirwani - University of Iowa
- Resource Type
- Book chapter
- Publication Details
- Algorithms – ESA 2007, pp.311-322
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/978-3-540-75520-3_29
- eISSN
- 1611-3349
- ISSN
- 0302-9743
- Language
- English
- Date published
- 2007
- Academic Unit
- Computer Science
- Record Identifier
- 9984259502002771
Metrics
9 Record Views