2014/04/02 by David Adjiashvili, Adjiashvili, David, Noy Rotbart +1
Computer Science · #05C78 #05C85 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #E.1 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2
paper · pdf · doi:10.48550/arxiv.1404.0588
openalex publication_date 2014/04/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate adjacency labeling schemes for graphs of bounded degree Δ= O(1). In particular, we present an optimal (up to an additive constant) log n + O(1) adjacency labeling scheme for bounded degree trees. The latter scheme is derived from a labeling scheme for bounded degree outerplanar graphs. Our results complement a similar bound recently obtained for bounded depth trees [Fraigniaud and Korman, SODA 10], and may provide new insights for closing the long standing gap for adjacency in trees [Alstrup and Rauhe, FOCS 02]. We also provide improved labeling schemes for bounded degree planar graphs. Finally, we use combinatorial number systems and present an improved adjacency labeling schemes for graphs of bounded degree Δ with (e+1)√(n) < Δ≤ n/5.