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 graphs in the plane. The considered graph classes include plane straight-line graphs, plane spanning trees, and connected plane straight-line graphs. 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, 23:467-479, 2007.