O conceito de explorar propriedades que um gráfico possui localmente pode ser levado ainda mais longe. Dawar, Grohe e Kreutzer em Excluindo um Menor consideram classes de gráficos que excluem localmente um menor e Dvorak, Kral e Thomas em Decidindo propriedades de primeira ordem para gráficos esparsos considerados classes de gráficos que têm expansão limitada localmente.
Ambas as classes são substituídas por classes de gráficos densos, apresentados por Nesetril e Ossona de Mendez.
Grohe anunciou esta semana na conferência Highlights que Grohe, Kreutzer e Siebertz. provaram que todas as propriedades dos gráficos definíveis na lógica de primeira ordem podem ser resolvidas em tempo quase linear em nenhuma classe densa de gráficos. Isso implica muitos resultados de rastreabilidade de parâmetros fixos em gráficos densos em nenhum lugar, por exemplo, para o conjunto dominante (conectado) e o núcleo do dígrafo (ambos parametrizados pelo tamanho da solução), a árvore Steiner (parametrizada pelo tamanho da árvore) e a satisfação do circuito ( parametrizado pela profundidade do circuito e pelo peso de Hamming da solução).