44 citations · 51 across the 11 of their papers we have counts for
12 papers
A Note on the Number of Regions in a Line Arrangement
Dickson Y. B. Annor, Michael S. Payne
For an arrangement of lines in the real projective plane, we denote by the number of regions into which the real projective plane is divided by the lines. Using Bojanowski'…
Intersecting longest paths in chordal graphs
Daniel J. Harvey, Michael S. Payne
We consider the size of the smallest set of vertices required to intersect every longest path in a chordal graph. Such sets are known as longest path transversals. We show that if…
Overlaid oriented Voronoi diagrams and the 1-Steiner tree problem
Michael S. Payne, Charl Ras, Marcus Volz
Overlaid oriented Voronoi diagrams (OOVDs) are known to provide useful data for the construction of optimal Euclidean -Steiner trees. The theoretical time complexity of construc…
Ramsey-type theorems for lines in 3-space
Jean Cardinal, Michael S. Payne, Noam Solomon
We prove geometric Ramsey-type statements on collections of lines in 3-space. These statements give guarantees on the size of a clique or an independent set in (hyper)graphs induce…
Bichromatic lines in the plane
Michael S. Payne
Given a set of red and blue points in the plane, a bichromatic line is a line containing at least one red and one blue point. We prove the following conjecture of Kleitman and Pinc…
Thoughts on Barnette's Conjecture
Helmut Alt, Michael S. Payne, Jens M. Schmidt +1
We prove a new sufficient condition for a cubic 3-connected planar graph to be Hamiltonian. This condition is most easily described as a property of the dual graph. Let be a pl…
On the general position subset selection problem
Michael S. Payne, David R. Wood
Let be the maximum integer such that every set of points in the plane with at most collinear contains a subset of points with no three collinear.…
Empty pentagons in point sets with collinearities
János Barát, Vida Dujmović, Gwenaël Joret +5
An empty pentagon in a point set P in the plane is a set of five points in P in strictly convex position with no other point of P in their convex hull. We prove that every finite s…
Progress on Dirac's Conjecture
Michael S. Payne, David R. Wood
In 1951, Gabriel Dirac conjectured that every set P of n non-collinear points in the plane contains a point in at least n/2-c lines determined by P, for some constant c. The follow…
Which point sets admit a k-angulation?
Michael S. Payne, Jens M. Schmidt, David R. Wood
For k >= 3, a k-angulation is a 2-connected plane graph in which every internal face is a k-gon. We say that a point set P admits a plane graph G if there is a straight-line drawin…
On the connectivity of visibility graphs
Michael S. Payne, Attila Pór, Pavel Valtr +1
The visibility graph of a finite set of points in the plane has the points as vertices and an edge between two vertices if the line segment between them contains no other points. T…
Unit distance graphs with ambiguous chromatic number
Michael S. Payne
First Laszlo Szekely and more recently Saharon Shelah and Alexander Soifer have presented examples of infinite graphs whose chromatic numbers depend on the axioms chosen for set th…