Arrange all Vertices on a Line

Question

Given a planar drawing of any bicubic graph, e.g.:

$\hskip1.7in$

Is it in general possible to arrange all vertices on a line?

Sure you'll have to bend some edges (without overlapping them) and I managed to do this for the cube, but is this possible in general?

... counterexamples are also welcome!

Answer 1

For your example graph, it is ok, as Misha Lavrov said. I recommend this web,

This graph:

    0--2;
    2--4;
    4--5;
    5--3;
    3--1;
    1--0;
    6--0;
    6--7;
    7--1;
    2--8;
    9--8;
    9--4;
    5--11;
    11--10;
    10--3;
    7--12;
    12--13;
    13--10;
    15--8;
    15--14;
    14--6;
    16--14;
    16--17;
    12--17;
    13--18;
    18--17;
    18--19;
    11--20;
    20--19;
    9--21;
    21--20;
    21--22;
    22--19;
    15--23;
    23--22;
    16--23;

Answer 2

In fact, if we can bend edges, every planar graph can be drawn so that all the vertices are on a line, without crossing. Note that this is different from at least two harder questions:

1. In a book embedding of thickness 2, we put all the vertices on a line, but require all edges to either stay below the line or above the line. Not all planar graphs can be drawn in this way; see this MSE question.
2. There are some difficult problems about planar drawings where all edges are straight lines, and as many vertices as possible are collinear; see, e.g. here. This is even more limiting; if we wanted all the vertices to be collinear in this problem, then our graph would need to be a subgraph of a path graph.

But with no further conditions on the edges (except the usual ones for a planar drawing), we can put all the vertices on a line.

To do this, begin by taking a planar drawing of the graph which does not necessarily have this property. Rotate the drawing, if necessary, so that all vertices have distinct $x$-coordinates. (A random rotation achieves this with probability $1$.) Now we will modify this drawing to move every vertex to the $x$-axis, one at a time.

Let the vertices have coordinates $(x_1, y_1), \dots, (x_n, y_n)$, with $x_1 < x_2 < \dots < x_n$, and let $\delta = \frac12 \min\{x_2 - x_1, x_3 - x_2, \dots, x_n - x_{n-1}\}$. For each $i = 1, \dots, n$, we will apply a transformation to the infinite vertical strip $\{(x,y) : |x - x_i| \le \delta\}$: within this vertical strip, we will move point $(x,y)$ to point $(x, y - y_i(1 - \frac{|x-x_i|}{\delta}))$.

This transformation is continuous, so the edges will remain plane curves. (In fact, if we start by assuming that the edges are piecewise linear curves, they will remain piecewise linear.)

This transformation is bijective, so the edges will still not intersect.

At the boundary of the vertical strip, where $|x-x_i|=\delta$, the transformation is the identity, so the graph remains intact when we apply the transformation within the vertical strip. Also, the interiors of the vertical strips are all disjoint, so the transformations for $i=1, \dots, n$ do not interact.

Finally, the transformation moves $(x_i,y_i)$ to $(x_i, 0)$. So after we do this transformation for every $i$, we will have put every vertex on the $x$-axis.

Here is an illustration (the vertical strips are highlighted). First, an embedding of a cube, not notable in any way except that (1) it's rotated to give all vertices different coordinates and (2) it's stretched out to make our later diagram easier to look at:

Second, here is the embedding we get after we apply a transformation to each of the vertical strips: