BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Given a link projection P and a link L, it is natural to ask whether it is possible that P is a projection of L. Taniyama answered this question for the cases in which L is a prime knot or link with crossing number at most five. Recently, Takimura settled the issue for the knot 62. We answer this question for the case in which L is the link L6n1.
Every simple drawing of a graph in the plane naturally induces a rotation system, but it is easy to exhibit a rotation system that does not arise from a simple drawing in the plane. We extend this to all surfaces: for every fixed surface Σ, there is a rotation system that does not arise from a simple drawing in Σ.
Borrowing László Székely's lively expression, we show that Hill's conjecture is "asymptotically at least 98.5% true". This long-standing conjecture states that the crossing number cr(Kn) of the complete graph Kn is H(n):=41⌊2n⌋⌊2n−1⌋⌊2n−2⌋⌊2n−3⌋, for all n≥3. This has been verified only for n≤12. Using flag algebras, Norin and Zwols obtained the best known asymptotic lower bound for the crossing number of complete bipartite graphs, from which it follows that for every sufficiently large n, cr(Kn)>0.905H(n). Also using flag algebras, we prove that asymptotically cr(Kn) is at least 0.985H(n). We also show that the spherical geodesic crossing number of Kn is asymptotically at least 0.996H(n).
In this work, we introduce and develop a theory of convex drawings of the complete graph Kn in the sphere. A drawing D of Kn is convex if, for every 3-cycle T of Kn, there is a closed disc ΔT bounded by D[T] such that, for any two vertices u,v with D[u] and D[v] both in ΔT, the entire edge D[uv] is also contained in ΔT. As one application of this perspective, we consider drawings containing a non-convex K5 that has restrictions on its extensions to drawings of K7. For each such drawing, we use convexity to produce a new drawing with fewer crossings. This is the first example of local considerations providing sufficient conditions for suboptimality. In particular, we do not compare the number of crossings {with the number of crossings in} any known drawings. This result sheds light on Aichholzer's computer proof (personal communication) showing that, for n≤12, every optimal drawing of Kn is convex. Convex drawings are characterized by excluding two of the five drawings of K5. Two refinements of convex drawings are h-convex and f-convex drawings. The latter have been shown by Aichholzer et al (Deciding monotonicity of good drawings of the complete graph, Proc.~XVI Spanish Meeting on Computational Geometry (EGC 2015), 2015) and, independently, the authors of the current article (Levi's Lemma, pseudolinear drawings of Kn, and empty triangles, \rbr{J. Graph Theory DOI: 10.1002/jgt.22167)}, to be equivalent to pseudolinear drawings. Also, h-convex drawings are equivalent to pseudospherical drawings as demonstrated recently by Arroyo et al (Extending drawings of complete graphs into arrangements of pseudocircles, submitted).
A {\em good drawing\/} of Kn is a drawing of the complete graph with n vertices in the sphere such that: no two edges with a common end cross; no two edges cross more than once; and no three edges all cross at the same point. Gioan's Theorem asserts that any two good drawings of Kn that have the same rotations of incident edges at every vertex are equivalent up to Reidemeister moves. At the time of preparation, 10 years had passed between the statement in the WG 2005 conference proceedings and our interest in the proposition. Shortly after we completed our preprint, Gioan independently completed a preprint.
Let K,L be convex sets in the plane. For normalization purposes, suppose that the area of K is 1. Suppose that a set Kn of n points are chosen independently and uniformly over K, and call a subset of K a {\em hole} if it does not contain any point in Kn. It is shown that w.h.p. the largest area of a hole homothetic to L is (1+o(1))logn/n. We also consider the problems of estimating the largest area convex hole, and the largest area of a convex polygonal hole with vertices in Kn. For these two problems we show that the answer is Θ(logn/n).
There are three main thrusts to this article: a new proof of Levi's Enlargement Lemma for pseudoline arrangements in the real projective plane; a new characterization of pseudolinear drawings of the complete graph; and proofs that pseudolinear and convex drawings of Kn have n2+O(nlogn) and O(n2), respectively, empty triangles. All the arguments are elementary, algorithmic, and self-contained.
The Joint Crossing Number problem asks for a simultaneous embedding of two disjoint graphs into one surface such that the number of edge crossings (between the two graphs) is minimized. It was introduced by Negami in 2001 in connection with diagonal flips in triangulations of surfaces, and subsequently investigated in a general form for small-genus surfaces. We prove that all of the commonly considered variants of this problem are NP-hard already in the orientable surface of genus 6, by a reduction from a special variant of the anchored crossing number problem of Cabello and Mohar.
It is very well-known that there are precisely two minimal non-planar graphs: K5 and K3,3 (degree 2 vertices being irrelevant in this context). In the language of crossing numbers, these are the only 1-crossing-critical graphs: they each have crossing number at least one, and every proper subgraph has crossing number less than one. In 1987, Kochol exhibited an infinite family of 3-connected, simple 2-crossing-critical graphs. In this work, we: (i) determine all the 3-connected 2-crossing-critical graphs that contain a subdivision of the Möbius Ladder V10; (ii) show how to obtain all the not 3-connected 2-crossing-critical graphs from the 3-connected ones; (iii) show that there are only finitely many 3-connected 2-crossing-critical graphs not containing a subdivision of V10; and (iv) determine all the 3-connected 2-crossing-critical graphs that do not contain a subdivision of V8.
The Harary-Hill Conjecture States that the number of crossings in any drawing of the complete graph Kn in the plane is at least Z(n):=41⌊2n⌋⌊2n−1⌋⌊2n−2⌋⌊2n−3⌋. In this paper, we settle the Harary-Hill conjecture for {\em shellable drawings}. We say that a drawing D of Kn is {\em s-shellable} if there exist a subset S={v1,v2,…,vs} of the vertices and a region R of D with the following property: For all 1≤i<j≤s, if Dij is the drawing obtained from D by removing v1,v2,…vi−1,vj+1,…,vs, then vi and vj are on the boundary of the region of Dij that contains R. For s≥n/2, we prove that the number of crossings of any s-shellable drawing of Kn is at least the long-conjectured value Z(n). Furthermore, we prove that all cylindrical, x-bounded, monotone, and 2-page drawings of Kn are s-shellable for some s≥n/2 and thus they all have at least Z(n) crossings. The techniques developed provide a unified proof of the Harary-Hill conjecture for these classes of drawings.
A "book" with k pages consists of a straight line (the "spine") and k half-planes (the "pages"), such that the boundary of each page is the spine. If a graph is drawn on a book with k pages in such a way that the vertices lie on the spine, and each edge is contained in a page, the result is a k-page book drawing (or simply a k-page drawing). The pagenumber of a graph G is the minimum k such that G admits a k-page embedding (that is, a k-page drawing with no edge crossings). The k-page crossing number nu_k(G) of G is the minimum number of crossings in a k-page drawing of G. We investigate the pagenumbers and k-page crossing numbers of complete bipartite graphs. We find the exact pagenumbers of several complete bipartite graphs, and use these pagenumbers to find the exact k-page crossing number of K_{k+1,n} for 3<=k<=6. We also prove the general asymptotic estimate lim_{k->oo} lim_{n->oo} nu_k(K_{k+1,n})/(2n^2/k^2)=1. Finally, we give general upper bounds for nu_k(K_{m,n}), and relate these bounds to the k-planar crossing numbers of K_{m,n} and K_n.
A "book with k pages" consists of a straight line (the "spine") and k half-planes (the "pages"), such that the boundary of each page is the spine. If a graph is drawn on a book with k pages in such a way that the vertices lie on the spine, and each edge is contained in a page, the result is a k-page book drawing (or simply a k-page drawing). The k-page crossing number nu_k(G) of a graph G is the minimum number of crossings in a k-page drawing of G. In this paper we investigate the k-page crossing numbers of complete graphs K_n. We use semidefinite programming techniques to give improved lower bounds on nu_k(K_n) for various values of k. We also use a maximum satisfiability reformulation to calculate the exact value of nu_k(K_n) for several values of k and n. Finally, we investigate the best construction known for drawing K_n in k pages, calculate the resulting number of crossings, and discuss this upper bound in the light of the new results reported in this paper.
A {\em convex hole} (or {\em empty convex polygon)} of a point set P in the plane is a convex polygon with vertices in P, containing no points of P in its interior. Let R be a bounded convex region in the plane. We show that the expected number of vertices of the largest convex hole of a set of n random points chosen independently and uniformly over R is Θ(logn/(loglogn)), regardless of the shape of R.
Richter and Thomassen proved that every graph has an edge e such that the crossing number $\ucr(G-e)$ of G−e is at least $(2/5)\ucr(G) - O(1)$. Fox and Cs. Tóth proved that dense graphs have large sets of edges (proportional in the total number of edges) whose removal leaves a graph with crossing number proportional to the crossing number of the original graph; this result was later strenghtened by Černý, Kynčl and G. Tóth. These results make our understanding of the {decay} of crossing numbers in dense graphs essentially complete. In this paper we prove a similar result for large sparse graphs in which the number of edges is not artificially inflated by operations such as edge subdivisions. We also discuss the connection between the decay of crossing numbers and expected crossing numbers, a concept recently introduced by Mohar and Tamon.
Around 1958, Hill described how to draw the complete graph Kn with [Z(n) :=1/4\lfloor \frac{n}{2}\rfloor \lfloor \frac{n-1}{2}\rfloor \lfloor \frac{n-2}{2}% \rfloor \lfloor \frac{n-3}{2}\rfloor] crossings, and conjectured that the crossing number $\crg (K_{n})$ of Kn is exactly Z(n). This is also known as Guy's conjecture as he later popularized it. Towards the end of the century, substantially different drawings of Kn with Z(n) crossings were found. These drawings are \emph{2-page book drawings}, that is, drawings where all the vertices are on a line ℓ (the spine) and each edge is fully contained in one of the two half-planes (pages) defined by ℓ. The \emph{2-page crossing number} of Kn, denoted by ν2(Kn), is the minimum number of crossings determined by a 2-page book drawing of Kn. Since $\crg(K_{n}) \leν_{2}(K_{n})$ and ν2(Kn)≤Z(n), a natural step towards Hill's Conjecture is the %(formally) weaker conjecture ν2(Kn)=Z(n), popularized by Vrt'o. %As far as we know, this natural %conjecture was first raised by Imrich Vrt'o in 2007. %Prior to this paper, results known for ν2(Kn) were basically %the same as for $\crg (K_n)$. Here In this paper we develop a novel and innovative technique to investigate crossings in drawings of Kn, and use it to prove that ν2(Kn)=Z(n). To this end, we extend the inherent geometric definition of k-edges for finite sets of points in the plane to topological drawings of Kn. We also introduce the concept of ≤≤k-edges as a useful generalization of ≤k-edges and extend a powerful theorem that expresses the number of crossings in a rectilinear drawing of Kn in terms of its number of (≤k)-edges to the topological setting.
Let f(n,k) be the minimum number of edges that must be removed from some complete geometric graph G on n points, so that there exists a tree on k vertices that is no longer a planar subgraph of G. In this paper we show that (1/2)k−1n2−2n≤f(n,k)≤2k−2n(n−2). For the case when k=n, we show that 2≤f(n,n)≤3. For the case when k=n and G is a geometric graph on a set of points in convex position, we show that at least three edges must be removed.
A graph is crossing-critical if the removal of any of its edges decreases its crossing number. This work is motivated by the following question: to what extent is crossing- criticality a property that is inherent to the structure of a graph, and to what extent can it be induced on a noncritical graph by multiplying (all or some of) its edges? It is shown that if a nonplanar graph G is obtained by adding an edge to a cubic polyhedral graph, and G is sufficiently connected, then G can be made crossing-critical by a suitable multiplication of edges.
Let P be a set of points in general position in the plane. Join all pairs of points in P with straight line segments. The number of segment-crossings in such a drawing, denoted by $\crg(P)$, is the \emph{rectilinear crossing number} of P. A \emph{halving line} of P is a line passing though two points of P that divides the rest of the points of P in (almost) half. The number of halving lines of P is denoted by h(P). Similarly, a k\emph{-edge}, 0≤k≤n/2−1, is a line passing through two points of P and leaving exactly k points of P on one side. The number of (≤k)-edges of P is denoted by E≤k(P). Let $\rcr(n)$, h(n), and E≤k(n) denote the minimum of $\crg(P)$, the maximum of h(P), and the minimum of E≤k(P), respectively, over all sets P of n points in general position in the plane. We show that the previously best known lower bound on E≤k(n) is tight for k<⌈(4n−2)/9⌉ and improve it for all k≥⌈(4n−2)/9⌉. This in turn improves the lower bound on $\rcr(n)$ from 0.37968(4n)+Θ(n3) to {277/729}\binom{n}{4}+Θ(n^{3})\geq 0.37997\binom{n}{4}+Θ(n^{3}).Wealsogivetheexactvaluesof\rcr(n)andh(n) foralln\leq27.Exactvalueswereknownonlyforn\leq18andoddn\leq21forthecrossingnumber,andforn\leq14andoddn\leq21$ for halving lines.
Devadoss asked: (1) can every polygon be convexified so that no internal visibility (between vertices) is lost in the process? Moreover, (2) does such a convexification exist, in which exactly one vertex is moved at a time (that is, using {\em single-vertex moves})? We prove the redundancy of the "single-vertex moves" condition: an affirmative answer to (1) implies an affirmative answer to (2). Since Aichholzer et al. recently proved (1), this settles (2).
Let S be a set of r red points and b=r+2d blue points in general position in the plane, with d≥0. A line ℓ determined by them is said to be balanced if in each open half-plane bounded by ℓ the difference between the number of red points and blue points is d. We show that every set S as above has at least r balanced lines. The main techniques in the proof are rotations and a generalization, sliding rotations, introduced here.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.