Given a graph like the one below, I try to pack/fit this graph into a fixed row $2D$ grid and use as few columns as possible. I can change the shape of the graph, but not the connectivity.
For example, the available grid has a fixed row size of $11$, and the original graph has a row size of $7$ as marked. Each $o$ represents a vertex and a vertex only connects to its adjacent neighbors. The black o are vertices on a row; every black $o$ only has one or two neighbors. The red $o$ are "bridges" connecting a different row of black $o$, which can have more than two neighbors.
There are two constraints for transformation:
- The previous adjacent vertices are still adjacent.
- Two nonadjacent vertices cannot be adjacent after transformation.
To simplify the question, I do not change the shape of the red vertices (although they may be transformed) and only change the shape of the black vertices.
A possible solution is shown below:
This problem can be thought of as using as few resources(columns) as to store the graph. The current solution is manually made.
I'm considering using a heuristic algorithm to solve it. For example, search for the chain of black $o$ that consume the fewest columns between the red parts without violating the constraints, but I think a better algorithm could exist for this problem.