Abstract
A (di)graph H has the Erdős-Pósa (EP) property for (butterfly) minors if there exists a function \(f: \mathbb {N} \rightarrow \mathbb {N}\) such that, for any \(k\in \mathbb {N}\) and any (di)graph G, either G contains at least k pairwise vertex-disjoint copies of H as (butterfly) minor, or there exists a subset T of at most f(k) vertices such that H is not a (butterfly) minor of \(G-T\). It is a well known result of Robertson and Seymour that an undirected graph has the EP property if and only if it is planar. This result was transposed to digraphs by Amiri, Kawarabayashi, Kreutzer and Wollan, who proved that a strong digraph has the EP property for butterfly minors if, and only if, it is a butterfly minor of a cylindrical grid. Contrary to the undirected case where a graph is planar if, and only if, it is the minor of some grid, not all planar digraphs are butterfly minors of a cylindrical grid. In this work, we characterize the planar digraphs that have a butterfly model in a cylindrical grid. In particular, this leads to a linear-time algorithm that decides whether a weakly 3-connected strong digraph has the EP property.
(Partially) supported by: FUNCAP MLC-0191-00056.01.00/22 and PNE-0112-00061.01.00/16, and CNPq 303803/2020-7, the CAPES-Cofecub project Ma 1004/23, by the project UCA JEDI (ANR-15-IDEX-01) and EUR DS4H Investments in the Future (ANR-17-EURE-004), the ANR Digraphs, the ANR Multimod and the Inria Associated Team CANOE. The full versions of omitted or sketched proofs can be found in [3].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Here, segment means line segment in the plane.
References
Amiri, A., Kawarabayashi, K., Kreutzer, S., Wollan, P.: The Erdos-Pósa property for directed graphs. arXiv preprint arXiv:1603.02504 (2016)
Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications, 2nd edn. Springer, London (2008). https://doi.org/10.1007/978-1-84800-998-1
Bensmail, J., Campos, V., Maia, A.K., Nisse, N., Silva, A.: Deciding the Erdös-Pósa property in \(3\)-connected digraphs (2023). www.inria.hal.science/hal-04084227
Duchet, P., Hamidoune, Y., Las Vergnas, M., Meyniel, H.: Representing a planar graph by vertical lines joining different levels. Discrete Math. 46, 319–321 (1983)
Erdős, P., Pósa, L.: On independent circuits contained in a graph. Can. J. Math. 17, 347–352 (1965)
Johnson, T., Robertson, N., Seymour, P., Thomas, R.: Directed tree-width. J. Comb. Theory Ser. B 82(1), 138–154 (2001)
Reed, B., Robertson, N., Seymour, P., Thomas, R.: Packing directed circuits. Combinatorica 16(4), 535–554 (1996). https://doi.org/10.1007/BF01271272
Robertson, N., Seymour, P.: Graph minors. V. Excluding a planar graph. J. Comb. Theory Ser. B 41, 92–114 (1986)
Robertson, N., Seymour, P.: Graph minors. VII. Disjoint paths on a surface. J. Comb. Theory Ser. B 45(2), 212–254 (1988)
Tamassia, R., Tollis, I.G.: A unified approach to visibility representations of planar graphs. Discrete Comput. Geom. 1, 321–341 (1986). https://doi.org/10.1007/BF02187705
West, D.B.: Introduction to Graph Theory, 2 edn. Prentice Hall (2000)
Whitney, H.: 2-isomorphic graphs. Am. J. Math. 55(1), 245–254 (1933)
Younger, D.: Graphs with interlinked directed circuits. In: Proceedings of the Mid-West Symposium on Circuit Theory, vol. 2 (1973)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Bensmail, J., Campos, V., Maia, A.K., Nisse, N., Silva, A. (2023). Deciding the Erdős-Pósa Property in 3-Connected Digraphs. In: Paulusma, D., Ries, B. (eds) Graph-Theoretic Concepts in Computer Science. WG 2023. Lecture Notes in Computer Science, vol 14093. Springer, Cham. https://doi.org/10.1007/978-3-031-43380-1_5
Download citation
DOI: https://doi.org/10.1007/978-3-031-43380-1_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-43379-5
Online ISBN: 978-3-031-43380-1
eBook Packages: Computer ScienceComputer Science (R0)