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= v1v2… vk in an edge-ordered graph is called increasing if (vivi+1) < (vi+1vi+2) for all i= 1 , … , k- 2 ;and it is called decreasing if (vivi+1) > (vi+1vi+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 α¯ (G) be the largest integer such that every edge-ordered straight-line drawing of G contains a monotone non-crossing path of length α¯ (G). Let τ¯ (G) be the largest integer such that every edge-ordered straight-line drawing of G contains a monotone non-crossing complete binary tree of τ¯ (G) edges. In this paper we show that α¯ (Kn) = Ω (log log n) , α¯ (Kn) = O(log n) , τ¯ (Kn) = Ω (log log log n) and τ¯(Kn)=O(nlogn). © 2021, Akadémiai Kiadó, Budapest, Hungary.