[
    {
        "id": "osp-17076",
        "type": "article-journal",
        "title": "Constrained Goal-directed Planar Graph Generation with Grammar-based Reinforcement Learning",
        "author": [
            {
                "family": "Hochuli",
                "given": "Nicolas"
            },
            {
                "family": "Miele",
                "given": "Lorenzo"
            },
            {
                "family": "Shea",
                "given": "Kristina"
            },
            {
                "family": "Stankovic",
                "given": "Tino"
            }
        ],
        "URL": "https://omanscience.com/en/articles/constrained-goal-directed-planar-graph-generation-with-grammar-based-reinforcement-learning",
        "language": "en",
        "issued": {
            "date-parts": [
                [
                    2026
                ]
            ]
        },
        "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."
    }
]