Drawing graphs on rectangular grids (Q1902892): Difference between revisions

The author considers the problem of embedding undirected graphs with \(n\) vertices of maximum degree 4 into rectangular grids. He presents an \(O(n^2)\)-algorithm that constructs an embedding for arbitrary 4-graphs into a \(2n \times 2n\) grid bending every edge at most twice. Firstly he constructs embeddings with at most three bends per wire into a \(2n \times 2n\) grid. Then the resulting embeddings can be modified to obtain at most two bends per wire without enlarging the grid area.