RRR. Bruce Richter

R. Bruce Richter

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


R. Bruce Richter has a total of 70 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Issue Information

    by Anton Bernshteyn, Eugene Lee, J. de Jong, R. Bruce Richter, Felix Bock, Johannes Pardey, Lúcia Draque Penso, Dieter Rautenbach, Jasine Babu, Deepu Benson, et al.

  • Open Access

    Strong 3‐Flow Conjecture for projective planar graphs

    by Jamie V. de Jong, R. Bruce Richter

    In 1972, Tutte posed the 3‐Flow Conjecture: that all 4‐edge‐connected graphs have a nowhere‐zero 3‐flow. This was extended by Jaeger et al. to allow vertices to have a prescribed, possibly nonzero difference (modulo 3) between the inflow and outflow. They conjectured that all 5‐edge‐connected graphs with a prescription function have a nowhere‐zero 3‐flow meeting that prescription. Kochol showed that replacing 4‐edge‐connected with 5‐edge‐connected would suffice to prove the 3‐Flow Conjecture and Lovász et al. showed that both conjectures hold if the edge connectivity condition is relaxed to 6‐edge‐connected. Both problems are still open for 5‐edge‐connected graphs. The 3‐Flow Conjecture was known to hold for planar graphs, as it is the dual of Grötzsch's Colouring Theorem. Steinberg and Younger provided the first direct proof using flows for planar graphs, as well as a proof for projective planar graphs. Richter et al. provided the first direct proof using flows of the Strong 3‐Flow Conjecture for planar graphs. We prove the Strong 3‐Flow Conjecture for projective planar graphs.

  • Open Access

    Convex drawings of the complete graph: topology meets geometry

    by Alan Arroyo, Dan McQuillan, R. Bruce Richter, Gelasio Salazar

    Convex drawings of the complete graph: topology meets geometry


  • Bounding the Number of Non-duplicates of the q-Side in Simple Drawings of $K_{p,q}$

    by R. Bruce Richter, André C. Silva, Orlando Lee

  • Open Access

    Extending drawings of complete graphs into arrangements of pseudocircles

    by Alan Arroyo, R. Bruce Richter, Matthew Sunohara

    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, either in 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.

  • Drawings of complete graphs in the projective plane

    by Alan Arroyo, Dan McQuillan, R. Bruce Richter, Gelasio Salazar, Matthew Sullivan

    Hill's Conjecture states that the crossing number cr ( K n ) of the complete graph K n in the plane (equivalently, the sphere) is 1 4 ⌊ n 2 ⌋ ⌊ n − 1 2 ⌋ ⌊ n − 2 2 ⌋ ⌊ n − 3 2 ⌋ = n 4 ∕ 64 + O ( n 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 n 4 ∕ 64 + O ( n 3 ) , thus matching asymptotically the conjectured value of cr ( K n ) . Let cr P ( G ) denote the crossing number of a graph G in the projective plane. Recently, Elkies proved that the expected number of crossings in a naturally defined random projective plane drawing of K n is ( n 4 ∕ 8 π 2 ) + O ( n 3 ) . In analogy with the relation of Moon's result to Hill's conjecture, Elkies asked if lim n → ∞   cr P ( K n ) ∕ n 4 = 1 ∕ 8 π 2 . We construct drawings of K n in the projective plane that disprove this.


  • Open Access

    Drawings of complete graphs in the projective plane

    by Alan Arroyo, Dan McQuillan, R. Bruce Richter, Gelasio Salazar, Matthew Sullivan

    Hill's Conjecture states that the crossing number $\text{cr}(K_n)$ of the complete graph $K_n$ in the plane (equivalently, the sphere) is $\frac{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=n^4/64 + O(n^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 $n^4/64+O(n^3)$, thus matching asymptotically the conjectured value of $\text{cr}(K_n)$. Let $\text{cr}_P(G)$ denote the crossing number of a graph $G$ in the projective plane. Recently, Elkies proved that the expected number of crossings in a naturally defined random projective plane drawing of $K_n$ is $(n^4/8\pi^2)+O(n^3)$. In analogy with the relation of Moon's result to Hill's conjecture, Elkies asked if $\lim_{n\to\infty} \text{cr}_P(K_n)/n^4=1/8\pi^2$. We construct drawings of $K_n$ in the projective plane that disprove this.

  • On 0-Rotatable Graceful Caterpillars

    by Atílio G. Luiz, C. N. Campos, R. Bruce Richter


  • Open Access

    Remarks on the structure of simple drawings of $K_n$

    by R. Bruce Richter, Matthew Sullivan

    In studying properties of simple drawings of the complete graph in the sphere, two natural questions arose for us: can an edge have multiple segments on the boundary of the same face? and is each face the intersection of sides of 3-cycles? The second is asserted to be obvious in two previously published articles, but when asked, authors of both papers were unable to provide a proof. We present a proof. The first is quite easily proved and the technique yields a third, even simpler, fact: no three edges at a vertex all have internal points incident with the same face.

  • Graphs with at most one crossing

    by André C. Silva, Alan Arroyo, R. Bruce Richter, Orlando Lee