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) . . . 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, . . . , k - 2; and it is called decreasing if (v(i)v(i)+ 1) > (v(i)+(1)v(i)+2) for all i = 1, . . . , 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 (alpha) over bar (G) be the largest integer such that every edge-ordered straight-line drawing of G contains a monotone non-crossing path of length (alpha) over bar (G). Let (tau) over bar (G) be the largest integer such that every edge-ordered straight-line drawing of G contains a monotone non-crossing complete binary tree of (tau) over bar (G) edges. In this paper we show that (alpha) over bar (K-n) = Omega(log log n), (alpha) over bar (K-n) = O(log n), (tau) over bar (K-n) = Omega(log log log n) and (tau) over bar (K-n) = Omega(root n log n).