Talk:Implicit graph

Reference Required for Rubik's Cube

The statement: "however, an implicit representation is necessary, as the state space of Rubik's Cube is too large to allow an algorithm to list all of its states" is correct IMO, since the Rubik's Cube has tens of quintillion states, I believe. That said, there should be a reference to this, especially since this statement could become outdated. In the 80's I could say that an implicit representation is required for a graph with just 1M states, but that is trivial today. 76.196.124.228 (talk)jj

 Done —David Eppstein (talk) 04:48, 9 December 2013 (UTC)

Candidates for the Implicit Graph Representation

I removed cographs as example of a candidate for the implicit graph conjecture. This is not true since cographs are a subset of permutation graphs and thus have an implicit representation. Instead I added disk graphs for which this question still seems to be open.

In fact, the only candidates for the IG Conjecture that I am aware of are the following: k-Dot Product graphs, (unit) disk graphs, line segment graphs, k-sphere graphs

References:

Sphere and Dot Product Representations of Graphs, Kang & Müller 2012, DOI 10.1007/s00454-012-9394-8

Integer realizations of disk and segment graphs, McDiarmid & Müller 2012, DOI 10.1016/j.jctb.2012.09.004

130.75.57.231 (talk) 13:17, 6 January 2016 (UTC)

But what you removed cographs from was a more specific question about whether they have a local adjacency labeling scheme. Do they? —David Eppstein (talk) 17:10, 6 January 2016 (UTC)

Yes, they have an adjacency labeling scheme (that is what I meant by implicit representation) since you can use the one for permutation graphs(assign each vertex 2 numbers between 1 and n to encode the permuation model). 130.75.57.231 (talk) 09:52, 7 January 2016 (UTC)

Ah, right. Please redo your change then. —David Eppstein (talk) 16:03, 7 January 2016 (UTC)