Gray code enumeration of plane straight-line graphs

O. Aichholzer, F. Aurenhammer, C. Huemer, and B. Vogtenhuber

Abstract:

We develop Gray code enumeration schemes for geometric straight-line graphs in the plane. The considered graph classes include plane graphs, connected plane graphs, and plane spanning trees. Previous results were restricted to the case where the underlying vertex set is in convex position.

Reference: O. Aichholzer, F. Aurenhammer, C. Huemer, and B. Vogtenhuber. Gray code enumeration of plane straight-line graphs. Graphs and Combinatorics (Springer), 23(5):467-479, 2007.