Abstract
A disk graph is the intersection graph of a set of disks in the plane. We consider the problem of assigning labels to vertices of a disk graph satisfying a sequence of distance constrains. Our objective is to minimize the distance between the smallest and the largest labels. We propose an on-line labeling algorithm on disk graphs, if the maximum and minimum diameters are bounded. We give the upper and lower bounds on its competitive ratio, and show that the algorithm is asymptotically optimal. In more detail we explore the case of distance constraints (2,1), and present two off-line approximation algorithms. The last one we call robust, i.e. it does not require the disks representation and either outputs a feasible labeling, or answers the input is not a unit disk graph.
Partially supported by EU ARACNE project HPRN-CT-1999-00112, by GACR 201/99/0242 and by the Ministry of Education of the Czech Republic as project LN00A056.
Partially supported by the DFG-Graduiertenkolleg “Effiziente Algorithmen und Mehrskalenmethoden”.
The work of this author was done while he was a visiting postdoc at DIMATIA-ITI partially supported by GAČR 201/99/0242 and by the Ministry of Education of the Czech Republic as project LN00A056. Also supported by Netherlands Organization for Scientific Research (NWO grant 047.008.006.)
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
H. L. Bodlaender, T. Kloks, R. B. Tan, AND J. Van Leeuwen, λ-coloring of graphs, in Proceedings of the 17th Annual Symp. on Theoretical Aspects of Computer Science (STACS 2000), H. Reichel and S. Tison, eds., Springer Verlag, Lecture Notes in Computer Science, vol. 1770, 2000, pp. 395–406.
H. Breu AND D. G. Kirkpatrick, Unit disc graph recognition is NP-hard, Computational Geometry: Theory and Applications, 9 (1998), pp. 3–24.
G. J. Chang AND D. Kuo, The L(2, 1)-labeling problem on graphs, SIAM Journal of Discrete Mathematics, 9 (1996), pp. 309–316.
B. N. Clark, C. J. Colbourn, AND D. S. Johnson, Unit disk graphs., Discrete Math., 86 (1990), pp. 165–177.
personal communication to Thomas Erlebach.
J. Fiala, J. Kratochvíl, AND T. Kloks, Fixed-parameter tractability of λ-colorings, in Graph-Theoretical Concepts in Computer Science, 25th WG’ 99, Ascona, no. 1665 in Lecture Notes in Computer Science, Springer Verlag, 1999, pp. 350–363.
J. P. Georges AND D. W. Mauro, On the size of graphs labeled with a condition at distance two, Journal of Graph Theory, 22 (1996), pp. 47–57.
J. R. Griggs AND R. K. Yeh, Labelling graphs with a condition at distance 2, SIAM Journal of Discrete Mathematics, 5 (1992), pp. 586–595.
A. Gyárfás AND J. Lehel, On-line and first fit colourings of graphs, Jornal of Graph Theory, 12 (1988), pp. 217–227.
W. K. Hale, Frequency assignment: Theory and applications, Proc. of the IEEE, 68 (1980), pp. 1497–1514.
P. Hliněný AND J. Kratochvíl, Representing graphs by disks and balls. to appear in Discrete Math.
R. A. Leese, Radio spectrum: a raw material for the telecommunications industry. 10th Conference of the European Consortium for Mathematics in Industry, Goteborg, 1998.
E. Malesińska, Graph theoretical models for frequency assignment problems, PhD thesis, Technical University of Berlin, 1997.
R. Peeters, On coloring j-unit sphere graphs, tech. rep., Dept. of Economics, Tilburg University, 1991.
V. Raghavan AND J. Spinrad, Robust algorithms for restricted domains manuscript submitted to Special Issue of Journal of Algorithms.
J. Van den Heuvel, R. A. Leese, AND M. A. Shepherd, Graph labeling and radio channel assignment, Journal of Graph Theory, 29 (1998), pp. 263–283.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fiala, J., Fishkin, A.V., Fomin, F.V. (2001). Online and Offline Distance Constrained Labeling of Disk Graphs. In: auf der Heide, F.M. (eds) Algorithms — ESA 2001. ESA 2001. Lecture Notes in Computer Science, vol 2161. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44676-1_39
Download citation
DOI: https://doi.org/10.1007/3-540-44676-1_39
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42493-2
Online ISBN: 978-3-540-44676-7
eBook Packages: Springer Book Archive