Compiling Crossing-free Geometric Graphs with Connectivity Constraint for Fast Enumeration, Random Sampling, and Optimization

Yu Nakahata, Takashi Horiyama, Shin-ichi Minato +1

Given $n$ points in the plane, we propose algorithms to compile connected crossing-free geometric graphs into directed acyclic graphs (DAGs). The DAGs allow efficient counting, enu…