Tomar un té, que va a ser mucho :)
dibujo esto con networkx, pero las principales medidas se podrían transferir con facilidad al graphviz.
El plan es el siguiente:
a) encontrar camarillas máxima (por si acaso, la máxima camarillas no son necesarias las mayores camarillas);
b) dibuje el gráfico y recuerde las coordenadas de los vértices que se usaron dibujando programm;
c) tomar las coordenadas de la camarilla, calcular el centro y el radio de las ciruelas que la rodean;
d) dibuje los círculos y coloree las vértices de las camarillas del mismo color (para las vértices en la intersección de 2 y más maxclases no es posible).
Con respecto a c): Fui perezoso para entender el círculo apretado, pero tener algo de tiempo puede hacerse fácilmente. En su lugar, calculé el "círculo aproximado": tomé como radio la longitud del borde más largo de la camarilla y lo multipliqué por 1.3. En realidad, con este enfoque, algunos nodos pueden quedar fuera, ya que solo el cociente sqrt (3) garantiza que todos estén dentro. Sin embargo, tomar sqrt (3) hará que el círculo sea demasiado grande (una vez más, no está ajustado). Como centro, tomé el medio del borde más grande.
import networkx as nx
from math import *
import matplotlib.pylab as plt
import itertools as it
def draw_circle_around_clique(clique,coords):
dist=0
temp_dist=0
center=[0 for i in range(2)]
color=colors.next()
for a in clique:
for b in clique:
temp_dist=(coords[a][0]-coords[b][0])**2+(coords[a][1]-coords[b][2])**2
if temp_dist>dist:
dist=temp_dist
for i in range(2):
center[i]=(coords[a][i]+coords[b][i])/2
rad=dist**0.5/2
cir = plt.Circle((center[0],center[1]), radius=rad*1.3,fill=False,color=color,hatch=hatches.next())
plt.gca().add_patch(cir)
plt.axis('scaled')
# return color of the circle, to use it as the color for vertices of the cliques
return color
global colors, hatches
colors=it.cycle('bgrcmyk')# blue, green, red, ...
hatches=it.cycle('/\|-+*')
# create a random graph
G=nx.gnp_random_graph(n=7,p=0.6)
# remember the coordinates of the vertices
coords=nx.spring_layout(G)
# remove "len(clique)>2" if you're interested in maxcliques with 2 edges
cliques=[clique for clique in nx.find_cliques(G) if len(clique)>2]
#draw the graph
nx.draw(G,pos=coords)
for clique in cliques:
print "Clique to appear: ",clique
nx.draw_networkx_nodes(G,pos=coords,nodelist=clique,node_color=draw_circle_around_clique(clique,coords))
plt.show()
Vamos a ver lo que obtenemos:
>> Clique to appear: [0, 5, 1, 2, 3, 6]
>> Clique to appear: [0, 5, 4]
Pico: 
Otro ejemplo con 3 maxcliques:
>> Clique to appear: [1, 4, 5]
>> Clique to appear: [2, 5, 4]
>> Clique to appear: [2, 5, 6]
