2

I know that arbitrary graphs can be embedded trivially in $\mathbb{R^3}$ and that planar graphs can be drawn on a plane using Schnyder's grid embedding algorithm after triangulation. And then there is also the $(i, i^2, i^3)$ moment curve approach..

What I am looking for is a non-crossing embedding of arbitrary graphs in multiple coplanar two-dimensional layers within $\mathbb{R^3}$ (a stack of $\mathbb{R^2}$ planes, $\mathbb{R^2} \times \mathbb{Z}$, discretized $\mathbb{R^3}$, 3D grid) just like the moment curve. But to make things more interesting I'd like the resulting embedding to look nice, i.e. minimizing the number of layers needed for an embedding and/or minimizing edge length. (Probably I want an embedding in $\mathbb{Z}^3$ or an minimum node distance constraint $|v_i - v_j| \ge 1$ for this to make sense)

I am new to this, so pointers to literature or more appropriate search keywords are highly welcome too. Perhaps this is a special/relaxed case of realization where distances between neighbors should be $1$, or maybe it is something along the lines of chip layout optimization. Does it make a difference if the graph is sparse? Is there a theory about embedding planar graphs in $\mathbb{R}^3$ to get shorter edge length?

Jonas Bötel
  • 121
  • I came naturally to this thread; I realize it was created a long time ago. I'm also interested in 3D graph drawing, but only of complete graphs $K_n$ of $n$ vertices. The handbook speaks about some methods and algorithms for an arbitrary graph which optimizes some properties. I was wondering: is there any known methods of drawing "nicely" complete graphs, which has a closed form solution? If not, what about embedding in a higher dimensional space $\mathbb{R}^M$ with $M<N$? Thank you! P.S. I leave "nicely" open to interpretation:) Maybe it could be in the direction that the OP was asking, or mo – Jorge del Val Jul 13 '21 at 12:50
  • @JorgedelVal: Perhaps this might help: Devillers, Olivier, Hazel Everett, Sylvain Lazard, Maria Pentcheva, and Stephen K. Wismath. "Drawing $K_n$ in three dimensions with one bend per edge." In International Symposium on Graph Drawing, pp. 83-88. Springer, Berlin, Heidelberg, 2005. – Joseph O'Rourke Jul 13 '21 at 15:19

2 Answers2

2

Let me offer two pointers. First, a common optimization is to minimize the number of bends in an orthogonal drawing. For example, here is a 2-bend drawing of $K_7$:
           K7
           (Image from S.-H. Poon's link.)

There are many papers on this topic. See also my MO question, "Min Bend Orthogonal Knots."

Second, there is a very good quite recent survey:

Handbook of Graph Drawing and Visualization. CRC Press. 2013. See the chapter by Vida Dujmović and Sue Whitesides, "Three-Dimensional Drawings." (CRC link)
           Handbook

Community
  • 1
Joseph O'Rourke
  • 149,182
  • 34
  • 342
  • 933
  • 1
    Your answer has been very helpful in many ways. I have a much better understanding of the actual problem now. Thank you! – Jonas Bötel Feb 24 '14 at 06:39
0

To answer my own question StackExchange style:

The concept you are looking is called [geometric] thickness of a graph. As described in the Handbook of Graph Drawing and Visualization (p. 473) mentioned by Joseph O'Rourke's excellent answer:

The thickness of a graph $\mathbf{G}$, denoted by $\theta(\mathbf{G})$, is the minimum $k \in \mathbb{N}$ such that the edge set of $\mathbf{G}$ can be partitioned into $k$ planar subgraphs.

Or as in an answer on planar graphs by David Eppstein:

[Thickness is] the minimum number of colors one needs to color the edges in a drawing of the graph in the plane such that edges of the same color do not cross.

Given such an edge coloring drawing the graph becomes a matter of drawing planar same-color subgraphs each on its own layer. Bad news is that obtaining the coloring or even testing for the minimum $k$ seems to be $\mathcal{NP}$-complete. Also edges are not necessarily short.

Indeed a more practical approach might be to construct an orthogonal drawing with known limits to both bends and volume (and therefore average edge length) as also suggested by Joseph O'Rourke. The Handbook of Graph Drawing and Visualization refers to various such constructions in chapter 14: Three-dimensional drawing algorithms.

Community
  • 1
Jonas Bötel
  • 121