A teoria dos grafos desempenha um papel fundamental tanto na matemática teórica quanto aplicada, na ciência da computação e na engenharia decomputação, influenciando significativamente o design e a análise de sistemascomplexos em domínios como arquiteturas de software, redes sociais e componentes elétricos. Um desafio crucial dentro deste campo é a minimização decruzamentos de arestas em desenhos de grafos, o que aumenta a clareza visuale reduz possíveis erros em circuitos eletrônicos e diagramas de fluxo de dados. Este trabalho investiga especificamente a minimização de cruzamentos dearestas em incorporações lineares de grafos, onde os vértices são alinhados aolongo de uma reta, referido como espinha, e as arestas são distribuídas emmúltiplos semi-planos, conhecidos como páginas, que se intersectam nestaespinha.Devido à natureza NP-Completa do problema, buscar soluções exatas éfrequentemente impraticável. Consequentemente, este estudo concentra-se naaplicação de meta-heurísticas, especificamente Recozimento Simulado e Pesquisa Local Iterada, como métodos robustos para enfrentar essa complexidade.Essas técnicas são exploradas em profundidade para demonstrar sua eficáciana navegação eficaz do espaço de busca, fornecendo assim soluções viáveis queaproximam o número mínimo de cruzamentos para várias configurações degrafos.Os resultados desta pesquisa destacam a adaptabilidade e o potencial dasabordagens meta-heurísticas no gerenciamento de desafios em teoria dos grafos. Por meio de análise comparativa e validação experimental, este trabalhoestabelece um modelo para estudos futuros para refinar e expandir as estraté-gias discutidas, oferecendo potencialmente novas vias para abordar problemasde otimização combinatória na teoria dos grafos e além.