Gray code enumeration of plane straight-line graphs

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


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. In Proc. $22^{nd}$ European Workshop on Computational Geometry EuroCG '06, pages 71-74, Delphi, Greece, 2006.