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

DOI10.1007/S10474-021-01166-2arXiv1703.05378MaRDI QIDQ6284379FDOQ6284379

Authors: Frank Duque, R. Fabila-Monroy, Carlos Hidalgo-Toscano, P. Pérez-Lantero 

Publication date: 15 March 2017

Abstract: An edge-ordered graph is a graph with a total ordering of its edges. A path $P=v_1{v}_{2}ldots{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,ldots,k-2$; it is called decreasing if $(v_i{v}_{i+1})<(v_{i+1}{v}_{i+2})$ for all $i=1,ldots,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 $overlinealpha(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 $overlinealpha(G)$. Let $overlineau(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 $overlineau(G)$. In this paper we show that $overlinealpha(K_n)=Omega(loglogn)$, $overlinealpha(K_n)=O(logn)$, $overlineau(K_n)=Omega(logloglogn)$ and $overlineau(K_n)=O(sqrtnlogn)$.

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38)

This page was built for publication: Non-crossing Monotone Paths and Binary Trees in Edge-ordered Complete Geometric Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6284379)