# Convex drawings of the complete graph: topology meets geometry

@article{Arroyo2021ConvexDO, title={Convex drawings of the complete graph: topology meets geometry}, author={Alan Arroyo and Dan McQuillan and R. Bruce Richter and Gelasio Salazar}, journal={Ars Mathematica Contemporanea}, year={2021} }

In this work, we introduce and develop a theory of convex drawings of the complete graph $K_n$ in the sphere. A drawing $D$ of $K_n$ is convex if, for every 3-cycle $T$ of $K_n$, there is a closed disc $\Delta_T$ bounded by $D[T]$ such that, for any two vertices $u,v$ with $D[u]$ and $D[v]$ both in $\Delta_T$, the entire edge $D[uv]$ is also contained in $\Delta_T$.
As one application of this perspective, we consider drawings containing a non-convex $K_5$ that has restrictions on its… Expand

#### Figures from this paper

#### 3 Citations

On Geometric Drawings of Graphs

- Computer Science
- 2018

This work characterize the minimal forbidden subdrawings for pseudolinear drawings and provides a polynomial-time algorithm for recognizing this family of drawings and introduces the notion pseudospherical drawings of Kn, a generalization of spherical drawings in which each edge is a minor arc of a great circle. Expand

Topological Drawings meet Classical Theorems from Convex Geometry

- Computer Science, Mathematics
- Graph Drawing
- 2020

In this article we discuss classical theorems from Convex Geometry in the context of topological drawings. In a simple topological drawing of the complete graph $K_n$, any two edges share at most one… Expand

Closing in on Hill's Conjecture

- Mathematics, Computer Science
- SIAM J. Discret. Math.
- 2019

It is shown that Hill's conjecture is "asymptotically at least 98.5% true", the best known asymptotic lower bound for the crossing number of complete bipartite graphs. Expand

#### References

SHOWING 1-10 OF 29 REFERENCES

Empty Triangles in Good Drawings of the Complete Graph

- Mathematics, Computer Science
- Graphs Comb.
- 2015

It is shown that the number of empty triangles in any good drawing of the complete graph $$K_n$$Kn with $$n$$n vertices is at least $$ n$$n. Expand

Shellable Drawings and the Cylindrical Crossing Number of $$K_{n}$$Kn

- Mathematics, Computer Science
- Discret. Comput. Geom.
- 2014

The techniques developed provide a unified proof of the Harary–Hill conjecture for shellable drawings and it is proved that all cylindrical, x-bounded, monotone, and 2-page drawings of K_n Kn are s-shellable for some s≥n/2 and thus they all have at least Z(n) = 14n2n-12n-22n-32 crossings. Expand

On the Erdos-Szekeres convex polygon problem

- Mathematics, Computer Science
- ArXiv
- 2016

The Erdos-Szekeres conjecture is nearly settled by showing that ENS(n) = 2 n + o (n) , which is the smallest integer such that any set of ENS points in the plane in general position contains n points in convex position. Expand

Complete Graph Drawings Up to Triangle Mutations

- Mathematics, Computer Science
- WG
- 2005

It is proved, constructively, that two complete graph drawings have the same subsketch if and only if they can be transformed into each other by a sequence of triangle mutations – or triangle switches. Expand

Levi's Lemma, pseudolinear drawings of Kn, and empty triangles

- Mathematics, Computer Science
- J. Graph Theory
- 2018

A new proof of Levi's Enlargement Lemma for pseudoline arrangements in the real projective plane is proved and proofs that pseudolinear and convex drawings of K_n have $n^2+{}$O$(n\log n)$ and O$( n^2)$, respectively, empty triangles are proved. Expand

Convex Quadrilaterals and k-Sets

- Mathematics
- 2003

We prove that the minimum number of convex quadrilaterals determined by n points in general position in the plane ‐ or in other words, the rectilinear crossing number of the complete graph Kn ‐ is at… Expand

Unavoidable Configurations in Complete Topological Graphs

- Computer Science, Mathematics
- Discret. Comput. Geom.
- 2003

It is shown that every complete topological graph with n vertices has a non-crossing subgraph isomorphic to any fixed tree with at most clog1/6n vertices. Expand

On the Combinatorial Classification of Nondegenerate Configurations in the Plane

- Computer Science, Mathematics
- J. Comb. Theory, Ser. A
- 1980

It is proved that for n ⩽ 5 every sequence essentially distinct from this one is realized geometrically by giving a complete classification of configurations by developing some basic notions of the geometry of “allowable sequences” in the course of proving this classification theorem. Expand

EMPTY SIMPLICES IN EUCLIDEAN-SPACE

- Mathematics
- 1987

Let P - {pi,p2,. . . ,p"} be an independent point-set in 1R'' (i.e., there are no d + 1 on a hyperplane). A simplex determined by d + 1 different points of P is called empty if it contains no point… Expand

Extension spaces of oriented matroids

- Mathematics, Computer Science
- Discret. Comput. Geom.
- 1993

It is proved that the extension space is spherical for the class of strongly euclidean oriented matroids, and it is shown that the subspace of realizable extensions is always connected but not necessarily spherical. Expand