Jellyfish graphs seem to be a fairly new idea. The term first appears around the turn of the century in an attempt to describe the topology of the Internet graph. The idea is that jellyfish graphs have a body (or cap) and lots of tentacles emanating from the core. In the case of the Internet, when looking at the Autonomous Systems level, the so called AS Internet graph can be thought of as a jellyfish graph. The Internet core corresponds to a clique or quasi-clique of high degree nodes. The rest of the graph can be seen as chains of lower degree nodes. Unlike other classes of graphs, jellyfish don't have a succinct definition. There is a formal definition here but it takes half a page and is not particularly pleasant.
Friday, May 29, 2009
Jellyfish
Jellyfish graphs seem to be a fairly new idea. The term first appears around the turn of the century in an attempt to describe the topology of the Internet graph. The idea is that jellyfish graphs have a body (or cap) and lots of tentacles emanating from the core. In the case of the Internet, when looking at the Autonomous Systems level, the so called AS Internet graph can be thought of as a jellyfish graph. The Internet core corresponds to a clique or quasi-clique of high degree nodes. The rest of the graph can be seen as chains of lower degree nodes. Unlike other classes of graphs, jellyfish don't have a succinct definition. There is a formal definition here but it takes half a page and is not particularly pleasant.
Friday, May 22, 2009
Starfish
Starfish graphs are made of one central cycle and a bunch of tentacles. When drawn appropriately they can look like starfish. More formally, a starfish graph has k vertices of degree 4 and k vertices of degree 2, with the degree-4 vertices arranged in a cycle and the degree-2 vertices making up each tentacle. Setting k=5 yields the traditional 5-tentacled beast. Apparently, the H-cover problem is NP-Complete even for simple graphs like starfish.
Subscribe to:
Posts (Atom)
