R. Bruce Richter
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
Research Subjects
Research Interests
R. Bruce Richter has a total of 70 co-authors. Here are the top co-authors by number of shared publications:
- Alan Arroyo
IST Austria
6 shared publications - Carsten Thomassen
Department of Applied Mathematics and Computer Science, Technical University of Denmark, Lyngby, Denmark
5 shared publications - Gelasio Salazar
Instituto de Física, Universidad Autónoma de San Luis Potosí, San Luis Potosí, Mexico
5 shared publications - Dan McQuillan
Department of Mathematics Norwich University
4 shared publications - Atílio Gomes Luiz
Campus Quixadá, Federal University of Ceará, Quixadá, Brazil
3 shared publications Dan McQuillan
Norwich University
3 shared publications
Latest Publications
- Open Access
- 6 June 2023
- Published by Wiley in Journal of Graph Theory
- Vol. 103 (4) , 603-605
Issue Information
- 6 June 2023
- Published by Wiley in Journal of Graph Theory
- Vol. 103 (4) , 603-605
Open AccessIssue Information
- Open Access
- 9 March 2023
- Published by Wiley in Journal of Graph Theory
- Vol. 103 (4) , 635-660
Strong 3‐Flow Conjecture for projective planar graphs
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.
- 9 March 2023
- Published by Wiley in Journal of Graph Theory
- Vol. 103 (4) , 635-660
Open AccessStrong 3‐Flow Conjecture for projective planar graphs
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
- 24 June 2022
- Published by University of Primorska Press in Ars Mathematica Contemporanea
- Vol. 22 (3) , #P3.04
Convex drawings of the complete graph: topology meets geometry
Convex drawings of the complete graph: topology meets geometry
- 24 June 2022
- Published by University of Primorska Press in Ars Mathematica Contemporanea
- Vol. 22 (3) , #P3.04
Open AccessConvex drawings of the complete graph: topology meets geometry
Convex drawings of the complete graph: topology meets geometry
- 22 August 2021
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 37 (6) , 2697-2701
Bounding the Number of Non-duplicates of the q-Side in Simple Drawings of $K_{p,q}$- 22 August 2021
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 37 (6) , 2697-2701
Bounding the Number of Non-duplicates of the q-Side in Simple Drawings of $K_{p,q}$- Open Access
Extending drawings of complete graphs into arrangements of pseudocircles
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.Open AccessExtending drawings of complete graphs into arrangements of pseudocircles
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. - 23 March 2021
- Published by Wiley in Journal of Graph Theory
- Vol. 97 (3) , 426-440
Drawings of complete graphs in the projective plane
Hill's Conjecture states that the crossing number of the complete graph in the plane (equivalently, the sphere) is . 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 , thus matching asymptotically the conjectured value of . Let 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 . In analogy with the relation of Moon's result to Hill's conjecture, Elkies asked if . We construct drawings of in the projective plane that disprove this.- 23 March 2021
- Published by Wiley in Journal of Graph Theory
- Vol. 97 (3) , 426-440
Drawings of complete graphs in the projective plane
Hill's Conjecture states that the crossing number of the complete graph in the plane (equivalently, the sphere) is . 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 , thus matching asymptotically the conjectured value of . Let 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 . In analogy with the relation of Moon's result to Hill's conjecture, Elkies asked if . We construct drawings of in the projective plane that disprove this.- Open Access
Drawings of complete graphs in the projective plane
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.Open AccessDrawings of complete graphs in the projective plane
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. - 3 September 2020
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 36 (6) , 1655-1673
On 0-Rotatable Graceful Caterpillars
- 3 September 2020
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 36 (6) , 1655-1673
On 0-Rotatable Graceful Caterpillars
- Open AccessRemarks on the structure of simple drawings of $K_n$
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.
Open AccessRemarks on the structure of simple drawings of $K_n$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.
- 1 November 2019
- Published by Elsevier in Discrete Mathematics
- Vol. 342 (11) , 3201-3207
Graphs with at most one crossing
- 1 November 2019
- Published by Elsevier in Discrete Mathematics
- Vol. 342 (11) , 3201-3207
Graphs with at most one crossing