Finding a subdivision of a digraph

We consider the following problem for oriented graphs and digraphs: Given a directed graph D, does it contain a subdivision of a prescribed digraph F? We give a number of examples of polynomial instances, several NP-completeness proofs as well as a number of conjectures and open problems.

Data and Resources

Additional Info

Field Value
Source https://inria.hal.science/hal-00720500
Author Bang-Jensen, Jørgen, Havet, Frédéric, Maia de Oliviera, Ana Karolinna
Maintainer CCSD
Last Updated November 4, 2026, 15:18 (UTC)
Created November 4, 2026, 15:18 (UTC)
Identifier Report N°: RR-8024
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Department of Mathematics and Computer Science [Odense] (IMADA) ; University of Southern Denmark = Syddansk Universitet (SDU)
creator Bang-Jensen, Jørgen
date 2012-07-24T00:00:00
harvest_object_id 1e5f7893-144b-4a61-9a44-b8d22a55b730
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2026-02-24T00:00:00
set_spec type:REPORT