Abstract
Planar graphs are central to applications across science and engineering, yet existing generators provide limited support for goal-directed generation under hard structural and geometric feasibility constraints. We propose a dataset-free method for generating planar graph embeddings by combining parametric graph grammars with safe reinforcement learning to optimize generic task-specific objectives while satisfying constraints during construction. We formulate the generation process as a constrained Markov decision process, where the graph grammar defines the state and action spaces. We further introduce an action projection that maps sampled actions toward state-dependent safe sets, improving constraint satisfaction during training. In contrast to classical graph generators and deep generative models, which typically offer limited goal-directed control or rely on weak constraint satisfaction, our method constructs feasible planar graph embeddings directly during generation. We also introduce a benchmark suite for constrained and goal-directed planar graph generation, together with classical and deep generative baselines. Across all benchmark tasks, our method consistently outperforms baselines while satisfying the formulated constraints.
Keywords
Publication details
- Journal
- Not available
- Open access
- Green open access
Cite this article
APA 7
Hochuli, N., Miele, L., Shea, K., & Stankovic, T. (2026). Constrained Goal-directed Planar Graph Generation with Grammar-based Reinforcement Learning. https://omanscience.com/en/articles/constrained-goal-directed-planar-graph-generation-with-grammar-based-reinforcement-learning
MLA 9
Hochuli, Nicolas, et al. "Constrained Goal-directed Planar Graph Generation with Grammar-based Reinforcement Learning." https://omanscience.com/en/articles/constrained-goal-directed-planar-graph-generation-with-grammar-based-reinforcement-learning.
Chicago (author–date)
Hochuli, Nicolas, Lorenzo Miele, Kristina Shea, and Tino Stankovic. 2026. "Constrained Goal-directed Planar Graph Generation with Grammar-based Reinforcement Learning." https://omanscience.com/en/articles/constrained-goal-directed-planar-graph-generation-with-grammar-based-reinforcement-learning.
Harvard
Hochuli, N., Miele, L., Shea, K. and Stankovic, T. (2026) 'Constrained Goal-directed Planar Graph Generation with Grammar-based Reinforcement Learning', Available at: https://omanscience.com/en/articles/constrained-goal-directed-planar-graph-generation-with-grammar-based-reinforcement-learning.
Vancouver
Hochuli N, Miele L, Shea K, Stankovic T. Constrained Goal-directed Planar Graph Generation with Grammar-based Reinforcement Learning. https://omanscience.com/en/articles/constrained-goal-directed-planar-graph-generation-with-grammar-based-reinforcement-learning
IEEE
N. Hochuli, L. Miele, K. Shea, and T. Stankovic, "Constrained Goal-directed Planar Graph Generation with Grammar-based Reinforcement Learning," https://omanscience.com/en/articles/constrained-goal-directed-planar-graph-generation-with-grammar-based-reinforcement-learning.