Técnicas espectrais para gênero de um gráfico

Uma pergunta genérica: existem técnicas espectrais para estimar o gênero de um gráfico? Estou interessado em gráficos bipartidos.

$\rho(G)$

Raio espectral de gráficos planares finitos e infinitos e de gráficos do gênero delimitado , Zdenek Dvorak e Bojan Mohar, JCTB 2010.

$g$

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

Podemos usar isso para estimar um limite inferior para o gênero de um gráfico, se o raio espectral do gráfico for grande o suficiente. Para um limite mais preciso da constante big-O, consulte o documento.

A propriedade como sendo um gráfico bipartido parece ajudar pouco aqui. Eles são capazes de fornecer uma instância bipartida em que a desigualdade nos gráficos planares é a melhor possível.

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

Veja: Jianer Chen, Saroja P. Kanchi e Arkady Kanevsky. Uma observação sobre o gênero gráfico aproximado . Information Processing Letters 61 (6): 317–322, 1997.