Optimal induced universal graphs and adjacency labeling for trees

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

We show that there exists a graph G with O(n) nodes, where any forest of n nodes is a node-induced subgraph of G. Furthermore, for constant arboricity k, the result implies the existence of a graph with O(nk) nodes that contains all n-node graphs as node-induced subgraphs, matching a Ω(nk) lower bound. The lower bound and previously best upper bounds were presented in Alstrup and Rauhe (FOCS'02). Our upper bounds are obtained through a log2 n + O(1) labeling scheme for adjacency queries in forests. We hereby solve an open problem being raised repeatedly over decades, e.g. in Kannan, Naor, Rudich (STOC 1988), Chung (J. of Graph Theory 1990), Fraigniaud and Korman (SODA 2010).
Original languageEnglish
Title of host publication2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)
Number of pages16
Publication date2015
Publication statusPublished - 2015
EventThe Annual Symposium on Foundations of Computer Science - DoubleTree Hotel, Berkeley, California, United States
Duration: 18 Oct 201520 Oct 2015
Conference number: 56


ConferenceThe Annual Symposium on Foundations of Computer Science
LocationDoubleTree Hotel
LandUnited States
ByBerkeley, California
SeriesSymposium on Foundations of Computer Science. Annual Proceedings


ID: 159731418