The Experts below are selected from a list of 759 Experts worldwide ranked by ideXlab platform
Janos Pach - One of the best experts on this subject based on the ideXlab platform.
-
beyond the richter thomassen conjecture
Symposium on Discrete Algorithms, 2016Co-Authors: Janos Pach, Natan Rubin, Gabor TardosAbstract:If two closed Jordan curves in the plane have precisely one point in common, then it is called a touching point. All other intersection points are called crossing points. The main result of this paper is a Crossing Lemma for closed curves: In any family of n pairwise Intersecting simple closed curves in the plane, no three of which pass through the same point, the number of crossing points exceeds the number of touching points by a factor of Ω((log log n)1/8).As a corollary, we prove the following long-standing conjecture of Richter and Thomassen: The total number of intersection points between any n pairwise Intersecting simple closed curves in the plane, no three of which pass through the same point, is at least (1 -- o(1))n2.
-
Geometric Intersection Patterns and the Theory of Topological Graphs
2015Co-Authors: Janos PachAbstract:The intersection graph of a set system S is a graph on the vertex set S, in which two vertices are connected by an edge if and only if the corresponding sets have nonempty intersection. It was shown by Tietze (1905) that every finite graph is the intersection graph of 3-dimensional convex polytopes. The analogous statement is false in any fixed dimension if the polytopes are allowed to have only a bounded number of faces or are replaced by simple geometric objects that can be described in terms of a bounded number of real parameters. Intersection graphs of various classes of geometric objects, even in the plane, have interesting structural and extremal properties. We survey problems and results on geometric intersection graphs and, more gener-ally, intersection patterns. Many of the questions discussed were originally raised by Berge, Erdős, Grünbaum, Hadwiger, Turán, and others in the context of classical topol-ogy, graph theory, and combinatorics (related, e.g., to Helly’s theorem, Ramsey theory, perfect graphs). The rapid development of computational geometry and graph drawing algorithms in the last couple of decades gave further impetus to research in this field. A topological graph is a graph drawn in the plane so that its vertices are represented by points and its edges by possibly Intersecting simple continuous curves connecting the corresponding point pairs. We give applications of the results concerning intersection patterns in the theory of topological graphs
-
beyond the richter thomassen conjecture
arXiv: Combinatorics, 2015Co-Authors: Janos Pach, Natan Rubin, Gabor TardosAbstract:If two closed Jordan curves in the plane have precisely one point in common, then it is called a {\em touching point}. All other intersection points are called {\em crossing points}. The main result of this paper is a Crossing Lemma for closed curves: In any family of $n$ pairwise Intersecting simple closed curves in the plane, no three of which pass through the same point, the number of crossing points exceeds the number of touching points by a factor of at least $\Omega((\log\log n)^{1/8})$. As a corollary, we prove the following long-standing conjecture of Richter and Thomassen: The total number of intersection points between any $n$ pairwise Intersecting simple closed curves in the plane, no three of which pass through the same point, is at least $(1-o(1))n^2$.
-
coloring kk free intersection graphs of geometric objects in the plane
The Journal of Combinatorics, 2012Co-Authors: Jacob Fox, Janos PachAbstract:The intersection graph of a collection C of sets is the graph on the vertex set C, in which C"1,C"2@?C are joined by an edge if and only if C"1@?C"2 0@?. Erdos conjectured that the chromatic number of triangle-free intersection graphs of n segments in the plane is bounded from above by a constant. Here we show that it is bounded by a polylogarithmic function of n, which is the first nontrivial bound for this problem. More generally, we prove that for any t and k, the chromatic number of every K"k-free intersection graph of n curves in the plane, every pair of which have at most t points in common, is at most (c"tlognlogk)^c^l^o^g^k, where c is an absolute constant and c"t only depends on t. We establish analogous results for intersection graphs of convex sets, x-monotone curves, semialgebraic sets of constant description complexity, and sets that can be obtained as the union of a bounded number of sets homeomorphic to a disk. Using a mix of results on partially ordered sets and planar separators, for large k we improve the best known upper bound on the number of edges of a k-quasi-planar topological graph with n vertices, that is, a graph drawn in the plane with curvilinear edges, no k of which are pairwise crossing. As another application, we show that for every @e>0 and for every positive integer t, there exist @d>0 and a positive integer n"0 such that every topological graph with n>=n"0 vertices, at least n^1^+^@e edges, and no pair of edges Intersecting in more than t points, has at least n^@d pairwise Intersecting edges.
-
coloring kk free intersection graphs of geometric objects in the plane
Symposium on Computational Geometry, 2008Co-Authors: Jacob Fox, Janos PachAbstract:The intersection graph of a collection C of sets is a graph on the vertex set C, in which C1,C2 ∈ C are joined by an edge if and only if C1 ∩ C2 ≠ O. Erdos conjectured that the chromatic number of triangle-free intersection graphs of n segments in the plane is bounded from above by a constant. Here we show that it is bounded by a polylogarithmic function of n, which is the first nontrivial bound for this problem. More generally, we prove that for any t and k, the chromatic number of every Kk-free intersection graph of n curves in the plane, every pair of which have at most t points in common, is at most (ct log n/log k)c log k, where c is an absolute constant and ct only depends on t. We establish analogous results for intersection graphs of convex sets, x-monotone curves, semialgebraic sets of constant description complexity, and sets that can be obtained as the union of a bounded number of sets homeomorphic to a disk.Using a mix of results on partially ordered sets and planar separators, for large k we improve the best known upper bound on the number of edges of a k-quasi-planar topological graph with n vertices, that is, a graph drawn in the plane with curvilinear edges, no k of which are pairwise crossing. As another application, we show that for every e > 0 and for every positive integer t, there exist δ > 0 and a positive integer n0 such that every topological graph with n ≥ n0 vertices, at least n1+e edges, and no pair of edges Intersecting in more than t points, has at least nδ pairwise Intersecting edges.
Jacob Fox - One of the best experts on this subject based on the ideXlab platform.
-
coloring kk free intersection graphs of geometric objects in the plane
The Journal of Combinatorics, 2012Co-Authors: Jacob Fox, Janos PachAbstract:The intersection graph of a collection C of sets is the graph on the vertex set C, in which C"1,C"2@?C are joined by an edge if and only if C"1@?C"2 0@?. Erdos conjectured that the chromatic number of triangle-free intersection graphs of n segments in the plane is bounded from above by a constant. Here we show that it is bounded by a polylogarithmic function of n, which is the first nontrivial bound for this problem. More generally, we prove that for any t and k, the chromatic number of every K"k-free intersection graph of n curves in the plane, every pair of which have at most t points in common, is at most (c"tlognlogk)^c^l^o^g^k, where c is an absolute constant and c"t only depends on t. We establish analogous results for intersection graphs of convex sets, x-monotone curves, semialgebraic sets of constant description complexity, and sets that can be obtained as the union of a bounded number of sets homeomorphic to a disk. Using a mix of results on partially ordered sets and planar separators, for large k we improve the best known upper bound on the number of edges of a k-quasi-planar topological graph with n vertices, that is, a graph drawn in the plane with curvilinear edges, no k of which are pairwise crossing. As another application, we show that for every @e>0 and for every positive integer t, there exist @d>0 and a positive integer n"0 such that every topological graph with n>=n"0 vertices, at least n^1^+^@e edges, and no pair of edges Intersecting in more than t points, has at least n^@d pairwise Intersecting edges.
-
coloring kk free intersection graphs of geometric objects in the plane
Symposium on Computational Geometry, 2008Co-Authors: Jacob Fox, Janos PachAbstract:The intersection graph of a collection C of sets is a graph on the vertex set C, in which C1,C2 ∈ C are joined by an edge if and only if C1 ∩ C2 ≠ O. Erdos conjectured that the chromatic number of triangle-free intersection graphs of n segments in the plane is bounded from above by a constant. Here we show that it is bounded by a polylogarithmic function of n, which is the first nontrivial bound for this problem. More generally, we prove that for any t and k, the chromatic number of every Kk-free intersection graph of n curves in the plane, every pair of which have at most t points in common, is at most (ct log n/log k)c log k, where c is an absolute constant and ct only depends on t. We establish analogous results for intersection graphs of convex sets, x-monotone curves, semialgebraic sets of constant description complexity, and sets that can be obtained as the union of a bounded number of sets homeomorphic to a disk.Using a mix of results on partially ordered sets and planar separators, for large k we improve the best known upper bound on the number of edges of a k-quasi-planar topological graph with n vertices, that is, a graph drawn in the plane with curvilinear edges, no k of which are pairwise crossing. As another application, we show that for every e > 0 and for every positive integer t, there exist δ > 0 and a positive integer n0 such that every topological graph with n ≥ n0 vertices, at least n1+e edges, and no pair of edges Intersecting in more than t points, has at least nδ pairwise Intersecting edges.
Santosh Devasia - One of the best experts on this subject based on the ideXlab platform.
-
on demand conflict resolution procedures for air traffic intersections
IEEE Transactions on Intelligent Transportation Systems, 2014Co-Authors: Jeff Yoo, Santosh DevasiaAbstract:This paper develops a provably safe on-demand conflict resolution procedure (CRP) for Intersecting routes in en route air-traffic control (ATC). Recent works have developed provably safe CRPs, which solve the conflict resolution for Intersecting routes in a local manner that leads to decoupling of CRPs for different intersections. However, such a CRP is inefficient because it is always on, i.e., even in the absence of conflicts. This always-on CRP (even without conflicts) leads to unwanted CRP maneuvers resulting in increased travel time, travel distance, and required fuel. This paper removes the inefficiency of always-on CRPs by developing provably safe CRPs that can be activated on demand (when conflicts appear) to accommodate an impending conflict. Conditions are developed to guarantee safety during activation and deactivation of the CRP and the proposed on-demand approach is illustrated through an example route intersection.
-
on demand conflict resolution procedures for air traffic intersections
American Control Conference, 2013Co-Authors: Jeff Yoo, Santosh DevasiaAbstract:This article presents a Conflict Resolution Procedure (CRP) for Intersecting routes in en-route Air Traffic Control (ATC). Recent works have developed provably-safe CRP, which solve the conflict resolution in a decoupled manner for en-route intersections. However, the original CRP for Intersecting routes is inefficient because it is always on - even in the absence of conflicts. In contrast, the current article develops provably-safe CRPs that can be activated on-demand to accommodate an impending conflict. Conditions are developed to guarantee safety during activation and deactivation, and the CRP is illustrated through an example route intersection.
Laurent Maerten - One of the best experts on this subject based on the ideXlab platform.
-
variation in slip on Intersecting normal faults implications for paleostress inversion
Journal of Geophysical Research, 2000Co-Authors: Laurent MaertenAbstract:Numerical models based on linear elasticity theory predict asymmetric slip distribution with a steep slip gradient near the line of intersection of Intersecting normal faults. They also predict a discrepancy between the direction of slip on the fault plane and the direction of resolved shear stress. Both variations in slip magnitude and direction are due to mechanical interaction between the faults with Intersecting patterns. These interactions cause local perturbations of the shear stress field acting on the plane of the adjacent fault. Field observations from the Chimney Rock area of central Utah show that slickensides on normal faults cutting the Navajo Sandstone change rake away from the expected downdip direction as the intersection line with adjacent faults is approached. The sense and magnitude of this change in orientation are similar to those computed by using the numerical models. The good correspondence between field observations and theoretical results from this paper not only provides insight into the mechanics of Intersecting faults, but suggests that care is required when using standard inverse methods to compute paleostresses from slickenside data. The slickenside orientation near intersection lines will generally not be in the direction of the remote maximum shear stress as resolved on the fault plane. A parameter study of this change in orientation provides helpful results for evaluating field data prior to a paleostress analysis.
Shihe Zhao - One of the best experts on this subject based on the ideXlab platform.
-
effects of hydraulic gradient Intersecting angle aperture and fracture length on the nonlinearity of fluid flow in smooth Intersecting fractures an experimental investigation
Geofluids, 2018Co-Authors: L F Fan, Shihe ZhaoAbstract:This study experimentally investigated the nonlinearity of fluid flow in smooth Intersecting fractures with a high Reynolds number and high hydraulic gradient. A series of fluid flow tests were conducted on one-inlet-two-outlet fracture patterns with a single intersection. During the experimental tests, the syringe pressure gradient was controlled and varied within the range of 0.20–1.80 MPa/m. Since the syringe pump used in the tests provided a stable flow rate for each hydraulic gradient, the effects of hydraulic gradient, Intersecting angle, aperture, and fracture length on the nonlinearities of fluid flow have been analysed for both effluent fractures. The results showed that as the hydraulic gradient or aperture increases, the nonlinearities of fluid flow in both the effluent fractures and the influent fracture increase. However, the nonlinearity of fluid flow in one effluent fracture decreased with increasing Intersecting angle or increasing fracture length, as the nonlinearity of fluid flow in the other effluent fracture simultaneously increased. In addition, the nonlinearities of fluid flow in each of the effluent fractures exceed that of the influent fracture.
