Enumerating Order Types for Small Point Sets with Applications

Order types are a means to characterize the combinatorial properties of a finite point configuration. In particular, the crossing properties of all straight-line segments spanned by a planar n-point set are reflected by its order type. We establish a complete and reliable data base for all possible order types of size n=10 or less. The data base includes a realizing point set for each order type in small integer grid representation. To our knowledge, no such project has been carried out before.We substantiate the usefulness of our data base by applying it to several problems in computational and combinatorial geometry. Problems concerning triangulations, simple polygonalizations, complete geometric graphs, and k-sets are addressed. This list of applications is not meant to be exhaustive. We believe our data base to be of value to many researchers who wish to examine their conjectures on small point configurations.     

Connected subgraphs with small degree sums in 3‐connected planar graphs

It is well‐known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3‐connected planar graph has an edge xy such that deg(x) + deg (y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we show that, for a given positive integer t, every 3‐connected planar graph G with |V(G)| ≥ t has a connected subgraph H of order t such that Σ_x∈V(H) deg_G(x) ≤ 8t − 1. As a tool for proving this result, we consider decompositions of 3‐connected planar graphs into connected subgraphs of order at least t and at most 2t − 1. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 191–203, 1999     

Bias matroids with unique graphical representations

Given a 3-connected biased graph Ω with three node-disjoint unbalanced circles, at most one of which is a loop, we describe how the bias matroid of Ω is uniquely represented by Ω.     

A superclass of Edge-Path-Tree graphs with few cliques

Edge-Path-Tree (EPT) graphs are intersection graphs of EPT matrices that is matrices whose columns are incidence vectors of edge-sets of paths in a given tree. EPT graphs have polynomially many cliques [M.C. Golumbic, R.E. Jamison, The edge intersection graphs of paths in a tree, Journal of Combinational Theory Series B 38 (1985) 8–22; C.L. Monma, V.K. Wey, Intersection graphs of paths in a tree, Journal of Combinational Theory Series B 41 (1986) 141–181]. Therefore, the problem of finding a clique of maximum weight in these graphs is solvable in strongly polynomial time. We extend this result to a proper superclass of EPT graphs.     

Characterizing graphic matroids by a system of linear equations

Given a rank-r   binary matroid we construct a system of O(r³)$O(r^3)$ linear equations in O(r²)$O(r^2)$ variables that has a solution over GF(2)$\mathrm{GF}(2)$ if and only if the matroid is graphic.     

Sparsity-certifying Graph Decompositions

We describe a new algorithm, the (k, ℓ)-pebble game with colors, and use it to obtain a characterization of the family of (k, ℓ)-sparse graphs and algorithmic solutions to a family of problems concerning tree decompositions of graphs. Special instances of sparse graphs appear in rigidity theory and have received increased attention in recent years. In particular, our colored pebbles generalize and strengthen the previous results of Lee and Streinu [12] and give a new proof of the Tutte-Nash-Williams characterization of arboricity. We also present a new decomposition that certifies sparsity based on the (k, ℓ)-pebble game with colors. Our work also exposes connections between pebble game algorithms and previous sparse graph algorithms by Gabow [5], Gabow and Westermann [6] and Hendrickson [9]. Ileana Streinu; Research of both authors funded by the NSF under grants NSF CCF-0430990 and NSF-DARPA CARGO CCR-0310661 to the first author.     

Spanning maximal planar subgraphs of random graphs

We study the threshold for the existence of a spanning maximal planar subgraph in the random graph G_{n, p} . We show that it is very near p = 1/n^? We also discuss the threshold for the existence of a spanning maximal outerplanar subgraph. This is very near p = 1/n^½.     

On the intersection of infinite matroids

We show that the infinite matroid intersection conjecture of Nash-Williams implies the infinite Menger theorem proved by Aharoni and Berger in 2009.We prove that this conjecture is true whenever one matroid is nearly finitary and the second is the dual of a nearly finitary matroid, where the nearly finitary matroids form a superclass of the finitary matroids.In particular, this proves the infinite matroid intersection conjecture for finite-cycle matroids of 2-connected, locally finite graphs with only a finite number of vertex-disjoint rays.