@article{9295,
abstract = {Hill's Conjecture states that the crossing number cr(๐พ๐) of the complete graph ๐พ๐ in the plane (equivalently, the sphere) is 14โ๐2โโ๐โ12โโ๐โ22โโ๐โ32โ=๐4/64+๐(๐3) . Moon proved that the expected number of crossings in a spherical drawing in which the points are randomly distributed and joined by geodesics is precisely ๐4/64+๐(๐3) , thus matching asymptotically the conjectured value of cr(๐พ๐) . Let cr๐(๐บ) denote the crossing number of a graph ๐บ in the projective plane. Recently, Elkies proved that the expected number of crossings in a naturally defined random projective plane drawing of ๐พ๐ is (๐4/8๐2)+๐(๐3) . In analogy with the relation of Moon's result to Hill's conjecture, Elkies asked if lim๐โโโcr๐(๐พ๐)/๐4=1/8๐2 . We construct drawings of ๐พ๐ in the projective plane that disprove this.},
author = {Arroyo Guevara, Alan M and Mcquillan, Dan and Richter, R. Bruce and Salazar, Gelasio and Sullivan, Matthew},
issn = {1097-0118},
journal = {Journal of Graph Theory},
publisher = {Wiley},
title = {{Drawings of complete graphs in the projective plane}},
doi = {10.1002/jgt.22665},
year = {2021},
}
@article{9468,
abstract = {Motivated by the successful application of geometry to proving the Harary--Hill conjecture for โpseudolinearโ drawings of $K_n$, we introduce โpseudosphericalโ drawings of graphs. A spherical drawing of a graph $G$ is a drawing in the unit sphere $\mathbb{S}^2$ in which the vertices of $G$ are represented as points---no three on a great circle---and the edges of $G$ are shortest-arcs in $\mathbb{S}^2$ connecting pairs of vertices. Such a drawing has three properties: (1) every edge $e$ is contained in a simple closed curve $\gamma_e$ such that the only vertices in $\gamma_e$ are the ends of $e$; (2) if $e\ne f$, then $\gamma_e\cap\gamma_f$ has precisely two crossings; and (3) if $e\ne f$, then $e$ intersects $\gamma_f$ at most once, in either a crossing or an end of $e$. We use properties (1)--(3) to define a pseudospherical drawing of $G$. Our main result is that for the complete graph, properties (1)--(3) are equivalent to the same three properties but with โprecisely two crossingsโ in (2) replaced by โat most two crossings.โ The proof requires a result in the geometric transversal theory of arrangements of pseudocircles. This is proved using the surprising result that the absence of special arcs (coherent spirals) in an arrangement of simple closed curves characterizes the fact that any two curves in the arrangement have at most two crossings. Our studies provide the necessary ideas for exhibiting a drawing of $K_{10}$ that has no extension to an arrangement of pseudocircles and a drawing of $K_9$ that does extend to an arrangement of pseudocircles, but no such extension has all pairs of pseudocircles crossing twice.
},
author = {Arroyo Guevara, Alan M and Richter, R. Bruce and Sunohara, Matthew},
issn = {08954801},
journal = {SIAM Journal on Discrete Mathematics},
number = {2},
pages = {1050--1076},
publisher = {Society for Industrial and Applied Mathematics},
title = {{Extending drawings of complete graphs into arrangements of pseudocircles}},
doi = {10.1137/20M1313234},
volume = {35},
year = {2021},
}
@inproceedings{9296,
abstract = { matching is compatible to two or more labeled point sets of size n with labels {1,โฆ,n} if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled convex sets of n points there exists a compatible matching with โ2nโโโโ edges. More generally, for any โ labeled point sets we construct compatible matchings of size ฮฉ(n1/โ) . As a corresponding upper bound, we use probabilistic arguments to show that for any โ given sets of n points there exists a labeling of each set such that the largest compatible matching has O(n2/(โ+1)) edges. Finally, we show that ฮ(logn) copies of any set of n points are necessary and sufficient for the existence of a labeling such that any compatible matching consists only of a single edge.},
author = {Aichholzer, Oswin and Arroyo Guevara, Alan M and Masรกrovรก, Zuzana and Parada, Irene and Perz, Daniel and Pilz, Alexander and Tkadlec, Josef and Vogtenhuber, Birgit},
booktitle = {15th International Conference on Algorithms and Computation},
isbn = {9783030682101},
issn = {16113349},
location = {Yangon, Myanmar},
pages = {221--233},
publisher = {Springer Nature},
title = {{On compatible matchings}},
doi = {10.1007/978-3-030-68211-8_18},
volume = {12635},
year = {2021},
}
@inproceedings{7994,
abstract = {In the recent study of crossing numbers, drawings of graphs that can be extended to an arrangement of pseudolines (pseudolinear drawings) have played an important role as they are a natural combinatorial extension of rectilinear (or straight-line) drawings. A characterization of the pseudolinear drawings of K_n was found recently. We extend this characterization to all graphs, by describing the set of minimal forbidden subdrawings for pseudolinear drawings. Our characterization also leads to a polynomial-time algorithm to recognize pseudolinear drawings and construct the pseudolines when it is possible.},
author = {Arroyo Guevara, Alan M and Bensmail, Julien and Bruce Richter, R.},
booktitle = {36th International Symposium on Computational Geometry},
isbn = {9783959771436},
issn = {18688969},
location = {Zรผrich, Switzerland},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum fรผr Informatik},
title = {{Extending drawings of graphs to arrangements of pseudolines}},
doi = {10.4230/LIPIcs.SoCG.2020.9},
volume = {164},
year = {2020},
}
@inproceedings{8732,
abstract = {A simple drawing D(G) of a graph G is one where each pair of edges share at most one point: either a common endpoint or a proper crossing. An edge e in the complement of G can be inserted into D(G) if there exists a simple drawing of G+e extending D(G). As a result of Leviโs Enlargement Lemma, if a drawing is rectilinear (pseudolinear), that is, the edges can be extended into an arrangement of lines (pseudolines), then any edge in the complement of G can be inserted. In contrast, we show that it is NP -complete to decide whether one edge can be inserted into a simple drawing. This remains true even if we assume that the drawing is pseudocircular, that is, the edges can be extended to an arrangement of pseudocircles. On the positive side, we show that, given an arrangement of pseudocircles A and a pseudosegment ฯ , it can be decided in polynomial time whether there exists a pseudocircle ฮฆฯ extending ฯ for which Aโช{ฮฆฯ} is again an arrangement of pseudocircles.},
author = {Arroyo Guevara, Alan M and Klute, Fabian and Parada, Irene and Seidel, Raimund and Vogtenhuber, Birgit and Wiedera, Tilo},
booktitle = {Graph-Theoretic Concepts in Computer Science},
isbn = {9783030604394},
issn = {0302-9743},
location = {Leeds, United Kingdom},
pages = {325--338},
publisher = {Springer Nature},
title = {{Inserting one edge into a simple drawing is hard}},
doi = {10.1007/978-3-030-60440-0_26},
volume = {12301},
year = {2020},
}
@inproceedings{7230,
abstract = {Simple drawings of graphs are those in which each pair of edges share at most one point, either a common endpoint or a proper crossing. In this paper we study the problem of extending a simple drawing D(G) of a graph G by inserting a set of edges from the complement of G into D(G) such that the result is a simple drawing. In the context of rectilinear drawings, the problem is trivial. For pseudolinear drawings, the existence of such an extension follows from Leviโs enlargement lemma. In contrast, we prove that deciding if a given set of edges can be inserted into a simple drawing is NP-complete. Moreover, we show that the maximization version of the problem is APX-hard. We also present a polynomial-time algorithm for deciding whether one edge uv can be inserted into D(G) when {u,v} is a dominating set for the graph G.},
author = {Arroyo Guevara, Alan M and Derka, Martin and Parada, Irene},
booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
isbn = {9783030358013},
issn = {16113349},
location = {Prague, Czech Republic},
pages = {230--243},
publisher = {Springer Nature},
title = {{Extending simple drawings}},
doi = {10.1007/978-3-030-35802-0_18},
volume = {11904},
year = {2019},
}
@article{6638,
abstract = {The crossing number of a graph G is the least number of crossings over all possible drawings of G. We present a structural characterization of graphs with crossing number one.},
author = {Silva, Andrรฉ and Arroyo Guevara, Alan M and Richter, Bruce and Lee, Orlando},
issn = {0012-365X},
journal = {Discrete Mathematics},
number = {11},
pages = {3201--3207},
publisher = {Elsevier},
title = {{Graphs with at most one crossing}},
doi = {10.1016/j.disc.2019.06.031},
volume = {342},
year = {2019},
}