Sur l'incorporation d'un graphe dans la grille avec le nombre minimum de courbures

Étant donné un graphe planaire G accompagné d'une représentation planaire P, une incorporation de grille préservant la région de G est une incorporation planaire de G dans la grille rectiligne qui a une représentation planaire isomorphe à P. Dans cet article, un algorithme est présenté qui calcule une incorporation de grille préservant la région avec le nombre minimum de courbures dans les arêtes. Cet algorithme utilise des techniques de flux de réseau et s'exécute en temps O (n² n), où n est le nombre de sommets du graphe. Des versions contraintes du problème sont également considérées, et la plupart des résultats sont étendus aux graphes k-gonaux, c'est-à-dire, aux graphes dont les arêtes sont des séquences de segments avec une pente multiple de {180 / k} degrés. Les applications des résultats ci-dessus peuvent être trouvées dans plusieurs domaines : la conception de circuits VLSI, le design architectural, la communication par lumière ou micro-ondes, les problèmes de transport, et la mise en page automatique de diagrammes similaires à des graphes.