Planar projections of graphs

We consider the point-set $P_{i}=(\cos(a_{i}+ib),\cos(a_{i}+(i+1)b),\ldots,\cos(a_{i}+(i+d-1)b))$ for some suitable $b$ and $a_{i}$s. For given $i,j\in\{1,2,\ldots,d\}$, the projection of these points in the $(i,j)$ plane lie on an ellipse. ∎

Let $d$ be such that $\dbinom{d}{2}\geq\lceil\dfrac{n}{4}\rceil$. We assume that $n=2k$, where $k$ is even, and find sets $S,T$ of $n/2$ points each in $\mathbb{R}^{d}$ such that the projections of $S$ and $T$ to two given axis-parallel planes lie on an ellipse, with the ellipse corresponding to $S$ always contained inside and congruent to the ellipse corresponding to $T$, as shown in Figure 1 (right).

The drawing of edges is now the same as in [4], which we explain for the sake of completeness.

We decompose the complete graph on each of $S,T$ into $k/2$ disjoint paths and draw their edges in $k/2$ planes such that each path contains exactly one pair of diametrically opposite vertices that are adjacent. Here, we use the phrase “diametrically opposite” for a pair of vertices if the points corresponding to them have exactly $k/2-1$ other points between them on the convex hull. This is illustrated in Figure 1 (a), where $v_{1},v_{5}$ are the diametrically opposite pair which are adjacent. Other diametrically opposite pairs are $\{v_{2},v_{6}\},\{v_{3},v_{7}\}$ etc, each of which shall be adjacent in a different plane.

Finally, we add edges between every vertex of $S$ and the diametrically opposite pair of $T$. That this can be done is shown in [4], by showing that there exist a set of parallel lines each passing through one point in $S$, and arguing by continuity that if the diametrically opposite pair is far enough, they may be joined to the points of $S$ without intersections. This is illustrated in Figure 1 (b). ∎

Let $H_{n}$, $M_{n}$ be the projection of $G_{n}$ on $XY$, $YZ$ planes respectively. Observe that if we fix the embedding of vertices of $G$ in $H$, then in $M$ we would have the freedom to move vertices along $Z$ axis because $z$ coordinate of vertices have not been fixed yet.

Figure 2 gives the construction of a graph $G_{14}$ with 14 vertices and $6\times 14-15=69$ edges.

Let us assume that we are given $H_{k},M_{k}$ which are the planar projections of $G_{k}$ on $XY,YZ$ planes respectively, such that $|E_{k}|=6k-15$.

We now show that we can add a vertex $v_{k+1}$ with 6 neighbors, such that three of the new edges are added to $H_{k}$ to obtain $H_{k+1}$ and the other three are added to $M_{k}$ to obtain $M_{k+1}$.

In $H_{k}$, we place $v_{k+1}$ inside a triangle whose vertices are disjoint from the vertices present on the convex hull of $M_{k}$ namely $v_{1},v_{2},v_{k}$. Now the $(x,y)$ coordinates of $v_{k+1}$ are fixed we can take the $z$ coordinate of $v_{k+1}$ to be a value strictly greater than the $z$ coordinate of $v_{k}$. Now in $M_{k}$($YZ$ plane) we can add $v_{k+1}$ by connecting $v_{k+1}$ to $v_{1},v_{2},v_{k}$.

We can always find a triangle whose vertices should not contain any one of $v_{1},v_{2},v_{k}$. If $k$ is odd we add $v_{k+1}$ inside the triangle $v_{6},v_{4},v_{k-1}$ in $H_{k}$ and if $k$ is even we add $v_{k+1}$ inside the triangle $v_{7},v_{8},v_{k}$ in $H_{k}$.

Since we have added 6 edges to the graph $G_{k}$ the new graph $G_{k+1}$ contains $6k-15+6=6(k+1)-15$. The vertex $v_{n+1}$ is also being mapped to a suitable point in $\mathbb{R}^{3}$.

Inductively using the above process, we can generate $G_{n}$ for all n such that $|E_{n}|=6n-15$.

Consider an embedding of $G(V,E)$ such that the edges of $G$ are covered by planar drawings in two (projected) planes. Let $XY$ and $YZ$ be the two planes and let $G_{1}=(V,E_{1})$ and $G_{2}=(V,E_{2})$ be the two planar sub-graphs respectively, which are projected on these planes.

Clearly we can assume that the embeddings of both $G_{1}$ and $G_{2}$ are maximally planar.

Let
$A$ to be the vertex with lowest $y$ coordinate value,
$B$ to be the vertex with highest $y$ coordinate value,
$C$ to be the vertex with second lowest $y$ coordinate value,
$D$ to be the vertex with second highest $y$ coordinate value.

Proof of Claim 3.3: Suppose for contradiction that $AC\notin G_{1}$. Since $G_{1}$ is maximally planar, there must be an edge $uv$ that intersects the line-segment joining $AC$. Therefore the $y$ co-ordinate of $u$ or the $y$ co-ordinate of $v$ must lie between the $y$ co-ordinates of $A$ and $C$, which contradicts the choice of $A,C$. The proof for $BD$ is identical.

We now consider two cases.

Case 1: $|E_{1}|<3n-6$ or $|E_{2}|<3n-6$. In this case, we have: $|E_{1}\cup E_{2}|=|E_{1}|+|E_{2}|-|E_{1}\cap E_{2}|\leq 6n-13-2=6n-15$.

Case 2: $|E_{1}|=|E_{2}|=3n-6$. In this case, we show that in addition to $AC$ and $BD$, the edge $AB$ also belongs to both $E_{1}$ and $E_{2}$, which shows that $|E_{1}\cup E_{2}|\leq 6n-15$.

Since $G_{1}$ has $3n-6$ edges, its convex hull is a triangle. By the definition of $A,B$, we see that $AB$ should be on the convex hull, and hence is an edge of $G_{1}$. Similarly, $AB$ belongs to $G_{2}$ as well.

This completes the proof of Theorem 3.2. ∎

Consider an embedding of $G(V,E)$ such that the edges of $G$ are covered by planar drawings in three (projected) planes. Let $XY$, $YZ$ and $ZX$ be the two planes and let $G_{1}=(V,E_{1})$, $G_{2}=(V,E_{2})$ and $G_{3}=(V,E_{3})$ be the three planar sub-graphs respectively, which are projected on these planes.

We may assume that $G_{1},G_{2},G_{3}$ are maximally planar.
Here we have to consider few cases:

Case 1: $|E_{1}|=|E_{2}|=|E_{3}|=3n-6$. In this case we use the same argument as Theorem 3.2, we get $|E_{2}\setminus E_{1}|=3n-9$, $|E_{3}\setminus E_{1}|=3n-9$.

$|E_{1}\cup E_{2}\cup E_{3}|\leq|E_{1}|+|E_{2}\setminus E_{1}|+|E_{3}\setminus E_{1}|$.

$\implies|E_{1}\cup E_{2}\cup E_{3}|\leq(3n-6)+(3n-9)+(3n-9)=9n-24$.

Case 2: $|E_{1}|=|E_{2}|=3n-6,|E_{3}|\leq 3n-7$. In this case if we use the same argument as Theorem 3.2 we get $|E_{2}\setminus E_{1}|=3n-9$.

Since $G_{1},G_{3}$ are maximally planar using Claim 3.3, we get $|E_{3}\setminus E_{1}|\leq 3n-7-2=3n-9$.

$\implies|E_{1}\cup E_{2}\cup E_{3}|\leq(3n-6)+(3n-9)+(3n-9)=9n-24$.

Case 3:$|E_{1}|=3n-6,|E_{2}|\leq 3n-7,|E_{3}|\leq 3n-7$.

Since $G_{1},G_{2},G_{3}$ are maximally planar using Claim 3.3, we get $|E_{3}\setminus E_{1}|\leq 3n-7-2=3n-9$.

$|E_{2}\setminus E_{1}|\leq 3n-7-2=3n-9$.

$\implies|E_{1}\cup E_{2}\cup E_{3}|\leq(3n-6)+(3n-9)+(3n-9)=9n-24$.

Case 4:$|E_{1}|\leq 3n-7,|E_{2}|\leq 3n-7,|E_{3}|\leq 3n-7$.

Since $G_{1},G_{2},G_{3}$ are maximally planar, using Claim 3.3, we get $|E_{3}\setminus E_{1}|\leq|E_{2}\setminus E_{1}|\leq 3n-7-2=3n-9$. Similarly $|E_{3}\setminus E_{1}|=\leq 3n-9$;

$\implies|E_{1}\cup E_{2}\cup E_{3}|\leq(3n-7)+(3n-9)+(3n-9)=9n-25$.

This completes the proof of Theorem 3.4.

Let $w_{1},w_{2},\ldots w_{k}$ be the vertices on the central path such that $w_{i}$ has an edge with $w_{i-1}$ and $w_{i+1}$. All the indices are taken modulo $k$. Also, let $L_{i}$ denote the set of leaf vertices adjacent to $w_{i}$.

We set the $x$ co-ordinate of $w_{i}$ to be $i$, and the $x$ co-ordinate of every vertex of $L_{i}$ to be $i+1$. Clearly the edges of the caterpillar drawn with the above embedding are non-crossing. ∎

Without loss of generality, let $v_{1},v_{2},\ldots v_{n}$ be the vertices on the cycle such that $v_{i}$ has an edge with $v_{i-1}$ and $v_{i+1}$ and $v_{1}$ be the vertex with smallest y coordinate value. All the indices are taken modulo $n$.

We first remove the edge between $v_{1}$ and $v_{n}$ so that the remaining graph is a path for which we use the previous lemma to construct the embedding.

Now to add back the edge $v_{1}v_{n}$, we have to make sure that none of the other edges intersect with the edge between $v_{1}$ and $v_{n}$. Let $slope_{i}$ to be the slope between $v_{1}$ and $v_{i}$, and note that this is positive for all $i$, since $v_{1}$ has the lowest y coordinate. Let $m=min_{i}\{slope_{i}\}$. We now draw a line $L$ through $v_{1}$ with slope less than $m$ and place the vertex $v_{n}$ on $L$, as illustrated in the figure below.