Non-crossing Monotone Paths and Binary Trees in Edge-ordered Complete Geometric Graphs

An edge-ordered graph is a graph with a total ordering of its edges. A path $P=v_1{v}_2\dots v_k$ in an edge-ordered graph is called increasing if $(v_i{v}_{i+1})>(v_{i+1}{v}_{i+2})$ for all $i=1,\dots ,k-2$; it is called decreasing if $(v_i{v}_{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 of 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 maximum integer such that every edge-ordered straight-line drawing of $G$ %under any edge labeling contains a monotone non-crossing path of length $\bar{\alpha }(G)$. Let $\bar{\tau }(G)$ be the maximum integer such that every edge-ordered straight-line drawing of $G$ %under any edge labeling contains a monotone non-crossing complete binary tree of size $\bar{\tau }(G)$. In this paper we show that $\bar{\alpha }(K_n)=\mathrm{\Omega }(\log \log n)$, $\overline \alpha(K_n) = O(\log n)$,$\overline \tau(K_n) = \Omega(\log\log \log n)$and$\overline \tau(K_n) = O(\sqrt{n \log n})$.