Summary: An edge-ordered graph is a graph with a total ordering of its edges. A path \(P = v_1v_2 \dots v_k\) in an edge-ordered graph is called increasing if \((v_iv_{i+1}) < (v_{i+1}v_{i+2})\) for all \(i = 1, \dots, k - 2\); and it is called decreasing if \((v_iv_{i+1}) > (v_{i+1}v_{i+2})\) for all \(i = 1, \dots, k -2\). We say that \(P\) is monotone if it is increasing or decreasing. A rooted tree \(T\) in an edge-ordered graph is called monotone if either every path from the root to a leaf is increasing or every path from the root to a leaf is decreasing.
Let \(G\) be a graph. In a straight-line drawing \(D\) of \(G\), its vertices are drawn as different points in the plane and its edges are straight line segments. Let \(\bar{\alpha}(G)\) be the largest integer such that every edge-ordered straight-line drawing of \(G\) contains a monotone non-crossing path of length \(\bar{\alpha}(G)\). Let \(\bar{\tau}(G)\) be the largest integer such that every edge-ordered straight-line drawing of \(G\) contains a monotone non-crossing complete binary tree of \(\bar{\tau}(G)\) edges. In this paper we show that \(\bar{\alpha}(K_n) = \Omega(\log\log n), \bar{\alpha}(K_n) = O(\log n), \bar{\tau}(K_n) = \Omega(\log \log \log n)\) and \(\bar{\tau}(K_n)=O(\sqrt{n\log n})\).