7
$\begingroup$

Problem. Given a tree do we need fewer lines in 3D than in 2D in order to draw it straightline and crossing-free?

(Asked 01.10.2016 by Alexander Wolff on page 20 of Volume 1 of the Lviv Scottish Book).

Clarification. For a given finite simple graph $G$ by $\rho^1_2(G)$ (resp. $\rho^1_3(G)$) we denote the minimal number of straight lines needed to cover all edges in a straight-line crossing-free drawing of the graph $G$ in 2D (resp. 3D). We are asking for a tree $T$ such that $\rho^1_3(T)<\rho^1_2(T)$.

The problem was originally asked 11.06.2016 by Oleg Verbitsky.

$\endgroup$
8
  • $\begingroup$ A tree $T$ on $n$ vertices can be drawn in the plane with $n-1$ noncrossing segments, exactly the number of edges of $T$. Maybe you didn't mean to restrict your question to trees? (The title and the body are different.) $\endgroup$ Mar 3, 2017 at 18:28
  • 2
    $\begingroup$ I think the OP considers 2 line segments to only count as 1 if they lie on the same line and are adjacent. $\endgroup$
    – Mosquite
    Mar 3, 2017 at 18:45
  • $\begingroup$ I'm fairly sure that you need the same number of lines in 2D and 3D to draw the trees. The trick to proving it is find a mapping from embeddings in 3D to embedding in 2D that preserves the number of lines used. $\endgroup$
    – Mosquite
    Mar 3, 2017 at 18:57
  • $\begingroup$ @Mosquite: Thanks, you must be right in your interpretation. $\endgroup$ Mar 3, 2017 at 19:09
  • $\begingroup$ If two edges in a drawing lie on the same line but have intermediate edges between them that don't, are they considered to be part of the same line or not? (i.e., are all edges on a 'line', for counting purposes, contiguous or not?) If the goal is to actually minimize the number of line segments (and so noncontiguous edges can't count as part of the same line) then I'm pretty sure any 3d drawing can actually be translated directly down to 2d. $\endgroup$ May 5, 2017 at 0:28

1 Answer 1

2
$\begingroup$

I'm not 100% sure how to prove this, but here is my candidate for an embedding in 2D that minimizes the number of lines used:

For each node in the tree if it has an even number of edges, $2e$ then embed pairs of edges on the same line (i.e. put the edge $\frac{\pi}{e}$ radians apart) so that the node uses $e$ lines in total; if the node has an odd number of edges, $2e + 1$ then do the same, but have one edge be on its own line (put it at some angle not used by the other edges) to use $e+1$ lines in total. This process is possible by making the embedding spread out enough that there is no crossing.

I believe that you cannot do better than this because an edge can be on the same line of at most one incident edge. Furthermore I believe you cannot do better in 3D as well for the same reason.

$\endgroup$
4
  • $\begingroup$ The drawing of the tree may be very bent, allowing to a straight line to cover many edges. We even don’t know whether exists there a constant $c>0$ such that any tree with $n$ vertices admits a planar (straight-line crossing-free) drawing which can be covered by $c\sqrt{n}$ straight lines. $\endgroup$ Mar 4, 2017 at 4:45
  • $\begingroup$ My embedding allows lines to cover more than 2 edges. The process is only concerned with how to embed the edges at a per node level. I would be interested to see a tree that can be drawn with less lines than my embedding, unless I misunderstand the problem (i.e. the OP may suppose that the lines can have gaps in the edges they cover). $\endgroup$
    – Mosquite
    Mar 6, 2017 at 18:15
  • $\begingroup$ Yes, they can have the gaps. The minimum number $segm(G)$ of segments without gaps in a planar drawing of a graph $G$ is a subject of another problem (see, for instance, references [14] and [19] in the paper [1] from the question). Clearly, $segm(G)\ge \rho^1_2(G)$ for any planar graph. It turns out, however, that $segm(G) = O(\rho^1_2(G)^2) $ for any connected planar graph $G$. You can read a proof of this result and more about relations between $segm(G)$ and $\rho^1_2(G)$ is Section 3.2 of paper [1]. $\endgroup$ Mar 9, 2017 at 16:18
  • $\begingroup$ Concerning trees, it is known (see again [14] or [19]) that ignoring additive constants $segm(T)$ is equal to a half of the number of vertices of $T$ of odd degree. $\endgroup$ Mar 9, 2017 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.