Graph theory plays a pivotal role in theoretical and applied mathematics, computing science, and computer engineering, significantly influencing the design and analysis of complex systems across domains such as software architectures, social networks, and electrical components. A crucial challenge within this field is the minimization of edge crossings in graph drawings, which enhances visual clarity and reduces potential errors in electronic circuits and data flow diagrams. This work specifically investigates the minimization of edge crossings in linear embeddings of graphs, where vertices are aligned along a singular linear axis, referred to as the spine, and edges are distributed across multiple semi-planes, known as pages, that intersect at this spine. Due to the NP-Complete nature of the problem, seeking exact solutions is often impractical. Consequently, this study focuses on the application of metaheuristics, specifically Simulated Annealing and Iterated Local Search, as robust methods to address this complexity. These techniques are explored in depth to demonstrate their efficacy in navigating the search space effectively, thereby providing feasible solutions that approximate the minimal crossing numbers for various graph configurations. The findings of this research highlight the adaptability and potential of metaheuristic approaches in managing challenges in graph theory. Through comparative analysis and experimental validation, this work establishes a framework for future studies to refine and expand upon the strategies discussed, potentially offering new avenues for addressing combinatorial optimization problems in graph theory and beyond.