Afficher la notice abrégée

There are Plane Spanners of Maximum Degree 4

hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorBONICHON, Nicolas
hal.structure.identifierSchool of Computer Science, Telecommunications, and Information Systems [DePaul] [CTI]
dc.contributor.authorKANJ, Iyad
hal.structure.identifierSchool of Computer Science, Telecommunications, and Information Systems [DePaul] [CTI]
hal.structure.identifierSchool of Computing [DePaul] [SOC]
dc.contributor.authorPERKOVIĆ, Ljubomir
hal.structure.identifierDepartment of Computer Science - Lafayette College
dc.contributor.authorXIA, Ge
dc.date.accessioned2024-04-15T09:41:36Z
dc.date.available2024-04-15T09:41:36Z
dc.date.created2014-03-20
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/197612
dc.description.abstractEnLet E be the complete Euclidean graph on a set of points embedded in the plane. Given a constant t >= 1, a spanning subgraph G of E is said to be a t-spanner, or simply a spanner, if for any pair of vertices u,v in E the distance between u and v in G is at most t times their distance in E. A spanner is plane if its edges do not cross. This paper considers the question: "What is the smallest maximum degree that can always be achieved for a plane spanner of E?" Without the planarity constraint, it is known that the answer is 3 which is thus the best known lower bound on the degree of any plane spanner. With the planarity requirement, the best known upper bound on the maximum degree is 6, the last in a long sequence of results improving the upper bound. In this paper we show that the complete Euclidean graph always contains a plane spanner of maximum degree at most 4 and make a big step toward closing the question. Our construction leads to an efficient algorithm for obtaining the spanner from Chew's L1-Delaunay triangulation.
dc.language.isoen
dc.title.enThere are Plane Spanners of Maximum Degree 4
dc.typeDocument de travail - Pré-publication
dc.subject.halInformatique [cs]/Géométrie algorithmique [cs.CG]
dc.identifier.arxiv1403.5350
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
hal.identifierhal-00966353
hal.version1
hal.audienceNon spécifiée
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00966353v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.au=BONICHON,%20Nicolas&KANJ,%20Iyad&PERKOVI%C4%86,%20Ljubomir&XIA,%20Ge&rft.genre=preprint


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée