Quantum Graph Drawing

Graph drawing is a fundamental area of algorithmic research with applications in network analysis, VLSI design, and data visualization. Despite decades of progress, many fundamental graph drawing problems remain computationally intractable. This thesis investigates how quantum computing can be leveraged to overcome these classical limitations, laying the foundations for Quantum Graph Drawing as a systematic and theoretically grounded research field. The contributions are organized into three main directions. First, quantum brute-force algorithms for NP-hard graph drawing problems are developed, achieving up to quadratic speedups over the best-known classical exact algorithms. Second, quantum techniques are applied to advanced algorithmic paradigms, including dynamic programming and divide-and-conquer approaches, with new algorithms for one-sided crossing minimization and a general framework for polynomial-time quantum dynamic programming. Third, the thesis investigates quantum time-space tradeoffs, establishing asymptotically optimal relationships between available quantum memory and achievable speedups. Overall, this thesis demonstrates that quantum computing provides a powerful framework for graph drawing, enabling systematic improvements across a broad range of algorithmic techniques and suggesting promising directions at the intersection of graph drawing and quantum computation.