Year 2020, Volume 7 , Issue 1, Pages 35 - 53 2020-02-29

Locally recoverable codes from planar graphs

Kathryn HAYMAKER [1] , Justin O'PELLA [2]


In this paper we apply Kadhe and Calderbank's definition of LRCs from convex polyhedra and planar graphs \cite{KAD} to analyze the codes resulting from 3-connected regular and almost regular planar graphs. The resulting edge codes are locally recoverable with availability two. We prove that the minimum distance of planar graph LRCs is equal to the girth of the graph, and we also establish a new bound on the rate of planar graph edge codes. Constructions of regular and almost regular planar graphs are given, and their associated code parameters are determined. In certain cases, the code families meet the rate bound.
Error-correction, Local recovery, Planar graphs, Availability, Rate bound
  • [1] H. J. Broersma, A. J. W. Duijvestijn, F. Göbel, Generating all 3-connected 4-regular planar graphs from the octahedron graph, J. Graph Theor. 17(5) (1993) 613–620.
  • [2] P. Gopalan, C. Huang, H. Simitci, S. Yekhanin, On the locality of codeword symbols, IEEE Trans. Inform. Theory 58(11) (2012) 6925–6934.
  • [3] M. Hasheminezhad, B. D. McKay, T. Reeves, Recursive generation of simple planar 5-regular graphs and pentangulations, Journal of Graph Algorithms and Applications 15(3) (2011) 417–436.
  • [4] S. Kadhe, R. Calderbank, Rate optimal binary linear locally repairable codes with small availability, In 2017 IEEE International Symposium on Information Theory (ISIT) (2017) 166–170.
  • [5] S. Kadhe, R. Calderbank, Rate optimal binary linear locally repairable codes with small availability, arXiv preprint, arXiv:1701.02456, 2017.
  • [6] M. Meringer, Fast generation of regular graphs and construction of cages, J. Graph Theor. 30(2) (1999) 137–146.
  • [7] M. Meringer, Regular planar graphs, available online at http://www.mathe2.uni-bayreuth.de/ markus/reggraphs.html, accessed 2009.
  • [8] N. Prakash, V. Lalitha, P. Vijay Kumar, Codes with locality for two erasures, In 2014 IEEE International Symposium on Information Theory (2014) 1962–1966.
  • [9] E. F. Schmeichel, S. L. Hakimi, On planar graphical degree sequences, SIAM J. Appl. Math. 32(3)(1977) 598–609.
  • [10] E. Steinitz, Vorlesungen {\"u}ber die Theorie der Polyeder: unter Einschlu{\ss} der Elemente der Topologie, volume 41, Springer-Verlag, 2013.
Primary Language en
Subjects Engineering
Journal Section Articles
Authors

Orcid: 0000-0001-5965-4197
Author: Kathryn HAYMAKER (Primary Author)

Orcid: 0000-0002-1381-4172
Author: Justin O'PELLA

Dates

Publication Date : February 29, 2020

Bibtex @research article { jacodesmath645021, journal = {Journal of Algebra Combinatorics Discrete Structures and Applications}, issn = {}, eissn = {2148-838X}, address = {}, publisher = {Yildiz Technical University}, year = {2020}, volume = {7}, pages = {35 - 53}, doi = {10.13069/jacodesmath.645021}, title = {Locally recoverable codes from planar graphs}, key = {cite}, author = {Haymaker, Kathryn and O'pella, Justin} }
APA Haymaker, K , O'pella, J . (2020). Locally recoverable codes from planar graphs . Journal of Algebra Combinatorics Discrete Structures and Applications , 7 (1) , 35-53 . DOI: 10.13069/jacodesmath.645021
MLA Haymaker, K , O'pella, J . "Locally recoverable codes from planar graphs" . Journal of Algebra Combinatorics Discrete Structures and Applications 7 (2020 ): 35-53 <https://dergipark.org.tr/en/pub/jacodesmath/issue/51990/645021>
Chicago Haymaker, K , O'pella, J . "Locally recoverable codes from planar graphs". Journal of Algebra Combinatorics Discrete Structures and Applications 7 (2020 ): 35-53
RIS TY - JOUR T1 - Locally recoverable codes from planar graphs AU - Kathryn Haymaker , Justin O'pella Y1 - 2020 PY - 2020 N1 - doi: 10.13069/jacodesmath.645021 DO - 10.13069/jacodesmath.645021 T2 - Journal of Algebra Combinatorics Discrete Structures and Applications JF - Journal JO - JOR SP - 35 EP - 53 VL - 7 IS - 1 SN - -2148-838X M3 - doi: 10.13069/jacodesmath.645021 UR - https://doi.org/10.13069/jacodesmath.645021 Y2 - 2019 ER -
EndNote %0 Journal of Algebra Combinatorics Discrete Structures and Applications Locally recoverable codes from planar graphs %A Kathryn Haymaker , Justin O'pella %T Locally recoverable codes from planar graphs %D 2020 %J Journal of Algebra Combinatorics Discrete Structures and Applications %P -2148-838X %V 7 %N 1 %R doi: 10.13069/jacodesmath.645021 %U 10.13069/jacodesmath.645021
ISNAD Haymaker, Kathryn , O'pella, Justin . "Locally recoverable codes from planar graphs". Journal of Algebra Combinatorics Discrete Structures and Applications 7 / 1 (February 2020): 35-53 . https://doi.org/10.13069/jacodesmath.645021
AMA Haymaker K , O'pella J . Locally recoverable codes from planar graphs. Journal of Algebra Combinatorics Discrete Structures and Applications. 2020; 7(1): 35-53.
Vancouver Haymaker K , O'pella J . Locally recoverable codes from planar graphs. Journal of Algebra Combinatorics Discrete Structures and Applications. 2020; 7(1): 35-53.