Sobre gráficos planares generalizados e gráficos externos planares generalizados

16

Qualquer planar , respectivamente, outerplanar gráfico satisfaz , respectivamente, , para cada subgráfico de . Além disso, gráficos planares (externos) podem ser reconhecidos em tempo polinomial.| E ' | 3 | V ' | - 6 | E ' | 2 | V ' | - 3 G = ( V , E ) GG=(V,E)|E|3|V|6
|E|2|V|3G=(V,E)G

O que se sabe sobre os gráficos tais que (resp. ) para cada subgrafo de ? É possível reconhecê-los em tempo polinomial?| E ' | 3 | V ' | - 6 | E ' | 2 | V ' | - 3 G = ( V , E ) GG=(V,E)|E|3|V|6|E|2|V|3G=(V,E)G

Editar (após a boa resposta de Eppstein): Qualquer gráfico plano satisfaz para cada subgrafo de com pelo menos três vértices . Portanto, "gráficos planares generalizados" seriam aqueles que satisfazem essa propriedade, e reconhecê-los no tempo polinomial parece ser uma questão aberta (interessante).G=(V,E)|E|3|V|6G=(V,E)G |V|3

Tobias Müller
fonte
Pela sua pergunta e edição, mudei o título; sinta-se à vontade para reverter.
User13136

Respostas:

16

Na notação de Lee e Streinu (citação abaixo), a segunda classe que você lista são os gráficos separados por (2,3). Eles fornecem um algoritmo para testar se um gráfico é (k, l) separado no tempo polinomial. No entanto, a situação com gráficos planares e é um pouco mais complicada, porque essa desigualdade não é verdadeira para todos os conjuntos de vértices (se fosse verdade, nenhum dois vértices poderia ser conectado por uma borda, porque ). Portanto, a classe de gráficos separados por (3,6) (em suas notações) consiste apenas em gráficos vazios. Provavelmente, seus algoritmos podem ser estendidos para gráficos para os quais a desigualdade é válida para todos os conjuntos de mais de dois vértices.|E|3|V|-632-6=0 0

Lee, Audrey; Streinu, Ileana (2008), "Algoritmos de jogos de seixos e gráficos esparsos", Discrete Mathematics 308 (8): 1425-1437, doi: 10.1016 / j.disc.2007.07.104 , arxiv: math / 0702129 .

David Eppstein
fonte
13

O que se sabe sobre "gráficos externos planares generalizados" ou (2,3) - gráficos separados? Alguns fatos adicionais à resposta de David Eppstein:

Em 1982, neste artigo (Corolários 1 e 2), Lovász e Yemini caracterizaram gráficos externos planares generalizados (em sua notação, gráficos independentes genéricos ) como aqueles gráficos com a propriedade de dobrar qualquer borda de G resultando em um gráfico que é a borda. união desdobrável de duas florestas.GG

Muito anteriormente, em 1970, Henneberg e Laman provaram que gráficos externos do plano generalizado podem ser obtidos recursivamente a partir de por três movimentos chamados de Henneberg (adição de um vértice grau 1, adição de vértice grau 2 e um certo tipo de adição de um vértice grau 3).K2

Essas caracterizações dão os primeiros reconhecimentos polinomiais para gráficos generalizados do plano externo.

Algumas observações relacionadas a gráficos planares generalizados podem ser encontradas na última seção deste documento . Penso que caracterizar e reconhecer gráficos planares generalizados ainda permanecem questões abertas muito interessantes.

user13136
fonte