Disjoint edges in geometric graphs

DOI10.1007/S00373-022-02563-2MaRDI QIDQ5925578zbMATH OpenOpenAlexWikidataFDO

Authors Nikita Chernega, Aleksandr A. Polyanskii, Rinat Sadykov

Publication date 28 September 2022

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2111.05425

zbMATH Keywords

disjoint edgesgeometric graphspointed vertex

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: A geometric graph is a graph drawn in the plane so that its vertices and edges are represented by points in general position and straight line segments, respectively. A vertex of a geometric graph is called pointed if it lies outside of the convex hull of its neighbours. We show that for a geometric graph with $n$ vertices and $e$ edges there are at least $$ pairs of disjoint edges provided that $2egeqn$ and all the vertices of the graph are pointed. Besides, we prove that if any edge of a geometric graph with $n$ vertices is disjoint from at most $m$ edges, then the number of edges of this graph does not exceed $n(sqrt1+8m+3)/4$ provided that $n$ is sufficiently large. These two results are tight for an infinite family of graphs.

Review text

This paper shows that in a geometric graph with \(n\) vertices and \(e\) edges there are at least \(\frac{n}{2}\binom{2e/n}{3}\) pairs of disjoint edges provided that \(2e\ge n\) and all the vertices of the graph are pointed. Moreover, it is proved that if any edge of a geometric graph with \(n\) vertices is disjoint from at most \(m\) edges, then the number of edges of this graph does not exceed \(n(\sqrt{1+8m}+3)/4\) provided that \(n\) is sufficiently large. Some open problems and conjectures are also mentioned in the paper.

Recommendations

• Disjoint edges in geometric graphs
• Combinatorial Geometry and Graph Theory
• Disjoint edges in topological graphs
• Geometric graphs with few disjoint edges
• Disjoint edges in separated hypergraphs
• Disjoint edges in complete topological graphs
• Disjoint edges in complete topological graphs
• Disjointness graphs of segments
• Geometric graphs with no three disjoint edges
• scientific article; zbMATH DE number 426342

Cites work

• Disjoint edges in geometric graphs
• Forcing disjoint segments in the plane
• Geometric graphs with few disjoint edges
• Geometric graphs with no three disjoint edges
• scientific article; zbMATH DE number 3643294 (Why is no real title available?)
• scientific article; zbMATH DE number 2109336 (Why is no real title available?)
• Note on geometric graphs
• On Sets of Distances of n Points
• On the smallest sets blocking simple perfect matchings in a convex geometric graph
• Some geometric applications of Dilworth's theorem
• The beginnings of geometric graph theory

Cited in

(12)

• Some geometric applications of Dilworth's theorem
• Geometric graphs with few disjoint edges
• Forcing disjoint segments in the plane
• Note on geometric graphs
• A generalization of an important lemma related to the Murty-Simon conjecture
• scientific article; zbMATH DE number 1054783 (Why is no real title available?)
• On convex geometric graphs with no \(k+1\) pairwise disjoint edges
• scientific article; zbMATH DE number 3407703 (Why is no real title available?)
• Disjoint edges in complete topological graphs
• Disjoint edges in geometric graphs
• Geometric graphs with no three disjoint edges
• Geometric graphs with no two parallel edges

This page was built for publication: Disjoint edges in geometric graphs

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