Acerca de las propiedades de la matriz de adyacencia cuando un gráfico es plano

21

1- ¿Hay alguna propiedad específica para la matriz de adyacencia cuando un gráfico es plano?
2- ¿Hay algo especial para calcular el permanente de la matriz de adyacencia cuando un gráfico es plano?

graph-theory co.combinatorics permanent marjoonjan
fuente
8
Al menos realice una revisión ortográfica antes de escribir sus preguntas. No es palanr, es plano
Suresh Venkat
:)) OK, claro, ¡prometo hacerlo! :)
marjoonjan
¿Qué tal un gráfico plano bipartito?
Mohammad Al-Turkistany
Personalmente, no me importa el gráfico plano bipartito, pero si tiene algo en mente, ¡es bienvenido! compártelo por favor!
marjoonjan
¿Es fácil calcular un gráfico plano bipartito permanente?
T ....

Respuestas:

25

Calcular gráficos determinantes y permanentes de planos es tan difícil como calcularlos en gráficos generales. Están completos para GapL y #P respectivamente. Vea este documento de Datta, Kulkarni, Limaye, Mahajan para más detalles.

Shiva Kintali
fuente
¿Es fácil calcular un gráfico plano bipartito permanente?
T ....
@Arul Sí, por el algoritmo FKT en.wikipedia.org/wiki/FKT_algorithm
Tyson Williams
15

Es más una propiedad de la matriz de incidencia que de la matriz de adyacencia, pero una propiedad importante de los gráficos planos es que son exactamente los gráficos cuyo matroide gráfico es el doble de otro matroide gráfico. La relación con las matrices de incidencia es que el gráfico matroide describe conjuntos de columnas independientes en la matriz.

David Eppstein
fuente
9

Existe una propiedad de la matriz de distancia (y no la matriz de adyacencia) de los gráficos planos restringidos que podrían ser de interés, la propiedad Monge . La propiedad Monge (debido a Gaspard Monge) para gráficos planos esencialmente significa que ciertos caminos más cortos no pueden cruzarse. Ver Wikipedia: Monge Array para una descripción formal de la propiedad Monge. Djidjev (WG 1996) ( documento en el sitio web de Djidjev ) y Fakcharoenphol y Rao (FOCS 2001) ( Video ) muestran cómo explotar las propiedades no cruzadas en algoritmos de ruta más corta.

Christian Sommer
fuente
6

No estoy seguro de qué tipo de propiedades está buscando, pero el radio espectral de los gráficos planos es una de esas cantidades (el valor absoluto máximo de un valor propio de la matriz adyacente). Ver por ejemplo este artículo .

Suresh Venkat
fuente
6

Si bien no está directamente relacionado con su pregunta, es posible que desee ver el trabajo sobre secuencias de grados de gráficos planos. No hay caracterizaciones conocidas de cuándo una secuencia de grados es la secuencia de grados de un gráfico plano. Sin embargo, hay una variedad de documentos interesantes sobre estos asuntos, que incluyen:

http://www.jstor.org/pss/2100346

Joseph Malkevitch
fuente