Locally recoverable codes from planar graphs
DOI:
https://doi.org/10.13069/jacodesmath.645021Keywords:
Error-correction, Local recovery, Planar graphs, Availability, Rate boundAbstract
In this paper we apply Kadhe and Calderbank's definition of LRCs from convex polyhedra and planar graphs [4] 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.
Received: 13 June 2019 Accepted: 17 August 2019Downloads
References
H. J. Broersma, A. J. W. Duijvestijn, and F. Göbel, Generating all $3$-connected $4$-regular planar graphs from the octahedron graph, J. Graph Theory 17(5) (1993) 613–620.
P. Gopalan, C. Huang, H. Simitci, and S. Yekhanin, On the locality of codeword symbols, IEEE Trans. Inform. Theory 58(11) (2012) 6925–6934.
M. Hasheminezhad, B. D. McKay, and T. Reeves, Recursive generation of simple planar $5$-regular graphs and pentangulations, J. Graph Algorithms Appl. 15(3) (2011) 417–436.
S. Kadhe and R. Calderbank, Rate optimal binary linear locally repairable codes with small availability, in: Proc. 2017 IEEE International Symposium on Information Theory (ISIT), Aachen, Germany (2017) 166–170.
S. Kadhe and R. Calderbank, Rate optimal binary linear locally repairable codes with small availability, arXiv:1701.02456 (2017).
M. Meringer, Fast generation of regular graphs and construction of cages, J. Graph Theory 30(2) (1999) 137–146.
M. Meringer, Regular planar graphs, available online at http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html.
N. Prakash, V. Lalitha, and P. V. Kumar, Codes with locality for two erasures, in: Proc. 2014 IEEE International Symposium on Information Theory, Honolulu, HI, USA (2014) 1962–1966.
E. F. Schmeichel and S. L. Hakimi, On planar graphical degree sequences, SIAM J. Appl. Math. 32(3) (1977) 598–609.
E. Steinitz and H. Rademacher, Vorlesungen über die Theorie der Polyeder: unter Einschluß der Elemente der Topologie, Grundlehren der mathematischen Wissenschaften, vol. 41, Springer-Verlag, Berlin (1934).
