Técnicas espectrales para el género de un gráfico.

Una pregunta genérica: ¿hay alguna técnica espectral para estimar el género de un gráfico? Estoy interesado en gráficos bipartitos.

$\rho(G)$

Radio espectral de gráficos planos finitos e infinitos y de gráficos del género acotado , Zdenek Dvorak y Bojan Mohar, JCTB 2010.

$g$

$g$$\rho(G) = \sqrt{8\Delta(G)} + O(\sqrt{g} \log g)$$\Delta(G)$$G$

Podemos usar esto para estimar un límite inferior para el género de un gráfico, si el radio espectral del gráfico es lo suficientemente grande. Para obtener un límite más preciso para la constante big-O, consulte el documento.

La propiedad como un gráfico bipartito parece ayudar poco aquí. Son capaces de proporcionar una instancia bipartita donde la desigualdad en los gráficos planos es la mejor posible.

$O(n^\epsilon)$$O(g\sqrt{n})$$\max\{4g, g+4n\}$$g$$n$

Ver: Jianer Chen, Saroja P. Kanchi y Arkady Kanevsky. Una nota sobre la aproximación del género gráfico . Information Processing Letters 61 (6): 317–322, 1997.