Optimal induced universal graphs and adjacency labeling for trees

TY - JOUR

T1 - Optimal induced universal graphs and adjacency labeling for trees

AU - Alstrup, Stephen

AU - Dahlgaard, Søren

AU - Knudsen, Mathias Bæk Tejs

PY - 2017/9

Y1 - 2017/9

N2 - In this article, we show that there exists a graph G with O(n) nodes such that any forest of n nodes is an 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 of arboricity k as node-induced subgraphs, matching a Ω(nk) lower bound of Alstrup and Rauhe. 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 by authors such as Kannan et al., Chung, and Fraigniaud and Korman.

AB - In this article, we show that there exists a graph G with O(n) nodes such that any forest of n nodes is an 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 of arboricity k as node-induced subgraphs, matching a Ω(nk) lower bound of Alstrup and Rauhe. 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 by authors such as Kannan et al., Chung, and Fraigniaud and Korman.

KW - Adjacency labeling

KW - Graph theory

KW - Induced universal graphs

KW - Trees

KW - XML

UR - http://www.scopus.com/inward/record.url?scp=85028082133&partnerID=8YFLogxK

U2 - 10.1145/3088513

DO - 10.1145/3088513

M3 - Journal article

AN - SCOPUS:85028082133

SN - 0004-5411

VL - 64

JO - Journal of the ACM

JF - Journal of the ACM

IS - 4

M1 - 27

ER -