License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2018.49
URN: urn:nbn:de:0030-drops-87621
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8762/
Jin, Yifei ;
Li, Jian ;
Zhan, Wei
Odd Yao-Yao Graphs are Not Spanners
Abstract
It is a long standing open problem whether Yao-Yao graphs YY_{k} are all spanners [Li et al. 2002]. Bauer and Damian [Bauer and Damian, 2012] showed that all YY_{6k} for k >= 6 are spanners. Li and Zhan [Li and Zhan, 2016] generalized their result and proved that all even Yao-Yao graphs YY_{2k} are spanners (for k >= 42). However, their technique cannot be extended to odd Yao-Yao graphs, and whether they are spanners are still elusive. In this paper, we show that, surprisingly, for any integer k >= 1, there exist odd Yao-Yao graph YY_{2k+1} instances, which are not spanners.
BibTeX - Entry
@InProceedings{jin_et_al:LIPIcs:2018:8762,
author = {Yifei Jin and Jian Li and Wei Zhan},
title = {{Odd Yao-Yao Graphs are Not Spanners}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {49:1--49:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Bettina Speckmann and Csaba D. T{\'o}th},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8762},
URN = {urn:nbn:de:0030-drops-87621},
doi = {10.4230/LIPIcs.SoCG.2018.49},
annote = {Keywords: Odd Yao-Yao Graph, Spanner, Counterexample}
}
|
Keywords: |
|
Odd Yao-Yao Graph, Spanner, Counterexample |
|
Collection: |
|
34th International Symposium on Computational Geometry (SoCG 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
08.06.2018 |
