Finding shortest non-trivial cycles in directed graphs on surfaces

Autor: Sergio Cabello, Éric Colin de Verdière, Francis Lazarus

Publikováno v: Journal of Computational Geometry, Vol 7, Iss 1 (2016)

Let $D$ be a weighted directed graph cellularly embedded in a surface of genus $g$, orientable or not, possibly with boundary. We describe algorithms to compute shortest non-contractible and shortest surface non-separating cycles in $D$, generalizing

Externí odkaz: https://doaj.org/article/5aed78efa2314631b1e2fa2ae7202dff

Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs

Autor: Dániel Marx, Vincent Cohen-Addad, Éric Colin de Verdière, Arnaud de Mesmay

Publikováno v: Journal of the ACM (JACM)
Journal of the ACM (JACM), Association for Computing Machinery, 2021, 68 (4), pp.1-26. ⟨10.1145/3450704⟩
SoCG 2019-35th International Symposium on Computational Geometry
SoCG 2019-35th International Symposium on Computational Geometry, Jun 2019, Portland, OR, United States
35th International Symposium on Computational Geometry (SoCG 2019)
Journal of the ACM

We prove essentially tight lower bounds, conditionally to the Exponential Time Hypothesis, for two fundamental but seemingly very different cutting problems on surface-embedded graphs: the Shortest Cut Graph problem and the Multiway Cut problem. A cu

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::866bd341eb3b8fc895297390742f4384
https://hal.archives-ouvertes.fr/hal-03432633

Embeddability of arrangements of pseudocircles and graphs on surfaces

Autor: Carolina Medina, Edgardo Roldán-Pensado, Éric Colin de Verdière, Gelasio Salazar

Publikováno v: Discrete and Computational Geometry
Discrete and Computational Geometry, Springer Verlag, 2020, 64 (2), pp.386-395. ⟨10.1007/s00454-019-00126-6⟩

A pseudocircle is a simple closed curve on some surface; an arrangement of pseudocircles is a collection of pseudocircles that pairwise intersect in exactly two points, at which they cross. Ortner proved that an arrangement of pseudocircles is embedd

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1323fe0b7be2197db6c4c08c23ddd77e

A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs with a Fixed Number of Terminals

Autor: Vincent Cohen-Addad, Arnaud de Mesmay, Éric Colin de Verdière

Publikováno v: Proceedings of the Twenty-Ninth ACM-SIAM Symposium on Discrete Algorithms
ACM-SIAM Symposium on Discrete Algorithms
ACM-SIAM Symposium on Discrete Algorithms, Jan 2018, New Orleans, United States
SIAM Journal on Computing
SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2021, 50 (1), pp.1-31. ⟨10.1137/18M1183297⟩

For an undirected edge-weighted graph $G$ and a set $R$ of pairs of vertices called pairs of terminals, a multicut is a set of edges such that removing these edges from $G$ disconnects each pair in $R$. We provide an algorithm computing a $(1+\vareps

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8f160676843cad6dda154737767d4ef0
http://arxiv.org/abs/1611.02966

A direct proof of the strong Hanani-Tutte theorem on the projective plane

Autor: Martin Tancer, Éric Colin de Verdière, Pavel Paták, Zuzana Patáková, Vojtěch Kaluža

Publikováno v: 24th International Symposium on Graph Drawing & Network Visualization
24th International Symposium on Graph Drawing & Network Visualization, 2016, Athens, Greece. ⟨10.1007/978-3-319-50106-2_35⟩
Journal of Graph Algorithms and Applications
Journal of Graph Algorithms and Applications, Brown University, 2017, 21 (5), pp.939-981. ⟨10.7155/jgaa.00445⟩
Lecture Notes in Computer Science ISBN: 9783319501055
Graph Drawing

We reprove the strong Hanani-Tutte theorem on the projective plane. In contrast to the previous proof by Pelsmajer, Schaefer and Stasi, our method is constructive and does not rely on the characterization of forbidden minors, which gives hope to exte

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a1c64cf68471cf54751c68fb60b5bb7d
https://hal.science/hal-01719743