Resumo
O número de cruzamentos de um grafo G é o menor número de cruzamentos entre arestas dentre todos os desenhos de G. Um grafo é dito planar quando existe um desenho no plano do mesmo que não contém cruzamentos. Desta forma, o número de cruzamentos de um grafo pode ser entendido como uma medida de não-planaridade de um grafo.Achar um desenho ótimo com relação ao número de cruzamentos de um g…