Search Results

Documents authored by Hubard, Alfredo

Document
DOI: 10.4230/LIPIcs.SoCG.2023.41
Disjoint Faces in Drawings of the Complete Graph and Topological Heilbronn Problems

Authors: Alfredo Hubard and Andrew Suk

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
Given a complete simple topological graph G, a k-face generated by G is the open bounded region enclosed by the edges of a non-self-intersecting k-cycle in G. Interestingly, there are complete simple topological graphs with the property that every odd face it generates contains the origin. In this paper, we show that every complete n-vertex simple topological graph generates at least Ω(n^{1/3}) pairwise disjoint 4-faces. As an immediate corollary, every complete simple topological graph on n vertices drawn in the unit square generates a 4-face with area at most O(n^{-1/3}). Finally, we investigate a ℤ₂ variant of Heilbronn’s triangle problem for not necessarily simple complete topological graphs.
Cite as

Alfredo Hubard and Andrew Suk. Disjoint Faces in Drawings of the Complete Graph and Topological Heilbronn Problems. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 41:1-41:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{hubard_et_al:LIPIcs.SoCG.2023.41,
  author =	{Hubard, Alfredo and Suk, Andrew},
  title =	{{Disjoint Faces in Drawings of the Complete Graph and Topological Heilbronn Problems}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{41:1--41:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.41},
  URN =		{urn:nbn:de:0030-drops-178917},
  doi =		{10.4230/LIPIcs.SoCG.2023.41},
  annote =	{Keywords: Disjoint faces, simple topological graphs, topological Heilbronn problems}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.41
Short Topological Decompositions of Non-Orientable Surfaces

Authors: Niloufar Fuladi, Alfredo Hubard, and Arnaud de Mesmay

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
We investigate short topological decompositions of non-orientable surfaces and provide algorithms to compute them. Our main result is a polynomial-time algorithm that for any graph embedded in a non-orientable surface computes a canonical non-orientable system of loops so that any loop from the canonical system intersects any edge of the graph in at most 30 points. The existence of such short canonical systems of loops was well known in the orientable case and an open problem in the non-orientable case. Our proof techniques combine recent work of Schaefer-Štefankovič with ideas coming from computational biology, specifically from the signed reversal distance algorithm of Hannenhalli-Pevzner. This result confirms a special case of a conjecture of Negami on the joint crossing number of two embeddable graphs. We also provide a correction for an argument of Negami bounding the joint crossing number of two non-orientable graph embeddings.
Cite as

Niloufar Fuladi, Alfredo Hubard, and Arnaud de Mesmay. Short Topological Decompositions of Non-Orientable Surfaces. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fuladi_et_al:LIPIcs.SoCG.2022.41,
  author =	{Fuladi, Niloufar and Hubard, Alfredo and de Mesmay, Arnaud},
  title =	{{Short Topological Decompositions of Non-Orientable Surfaces}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{41:1--41:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.41},
  URN =		{urn:nbn:de:0030-drops-160492},
  doi =		{10.4230/LIPIcs.SoCG.2022.41},
  annote =	{Keywords: Computational topology, embedded graph, non-orientable surface, joint crossing number, canonical system of loop, surface decomposition}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.17
Consistent Sets of Lines with no Colorful Incidence

Authors: Boris Bukh, Xavier Goaoc, Alfredo Hubard, and Matthew Trager

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
We consider incidences among colored sets of lines in {R}^d and examine whether the existence of certain concurrences between lines of k colors force the existence of at least one concurrence between lines of k+1 colors. This question is relevant for problems in 3D reconstruction in computer vision.
Cite as

Boris Bukh, Xavier Goaoc, Alfredo Hubard, and Matthew Trager. Consistent Sets of Lines with no Colorful Incidence. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bukh_et_al:LIPIcs.SoCG.2018.17,
  author =	{Bukh, Boris and Goaoc, Xavier and Hubard, Alfredo and Trager, Matthew},
  title =	{{Consistent Sets of Lines with no Colorful Incidence}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{17:1--17:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.17},
  URN =		{urn:nbn:de:0030-drops-87308},
  doi =		{10.4230/LIPIcs.SoCG.2018.17},
  annote =	{Keywords: Incidence geometry, image consistency, probabilistic construction, algebraic construction, projective configuration}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.43
Shortest Path Embeddings of Graphs on Surfaces

Authors: Alfredo Hubard, Vojtech Kaluža, Arnaud de Mesmay, and Martin Tancer

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
The classical theorem of Fáry states that every planar graph can be represented by an embedding in which every edge is represented by a straight line segment. We consider generalizations of Fáry's theorem to surfaces equipped with Riemannian metrics. In this setting, we require that every edge is drawn as a shortest path between its two endpoints and we call an embedding with this property a shortest path embedding. The main question addressed in this paper is whether given a closed surface S, there exists a Riemannian metric for which every topologically embeddable graph admits a shortest path embedding. This question is also motivated by various problems regarding crossing numbers on surfaces. We observe that the round metrics on the sphere and the projective plane have this property. We provide flat metrics on the torus and the Klein bottle which also have this property. Then we show that for the unit square flat metric on the Klein bottle there exists a graph without shortest path embeddings. We show, moreover, that for large g, there exist graphs G embeddable into the orientable surface of genus g, such that with large probability a random hyperbolic metric does not admit a shortest path embedding of G, where the probability measure is proportional to the Weil-Petersson volume on moduli space. Finally, we construct a hyperbolic metric on every orientable surface S of genus g, such that every graph embeddable into S can be embedded so that every edge is a concatenation of at most O(g) shortest paths.
Cite as

Alfredo Hubard, Vojtech Kaluža, Arnaud de Mesmay, and Martin Tancer. Shortest Path Embeddings of Graphs on Surfaces. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{hubard_et_al:LIPIcs.SoCG.2016.43,
  author =	{Hubard, Alfredo and Kalu\v{z}a, Vojtech and de Mesmay, Arnaud and Tancer, Martin},
  title =	{{Shortest Path Embeddings of Graphs on Surfaces}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{43:1--43:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.43},
  URN =		{urn:nbn:de:0030-drops-59356},
  doi =		{10.4230/LIPIcs.SoCG.2016.43},
  annote =	{Keywords: Graph embedding, surface, shortest path, crossing number, hyperbolic geometry}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.300
Limits of Order Types

Authors: Xavier Goaoc, Alfredo Hubard, Rémi de Joannis de Verclos, Jean-Sébastien Sereni, and Jan Volec

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
The notion of limits of dense graphs was invented, among other reasons, to attack problems in extremal graph theory. It is straightforward to define limits of order types in analogy with limits of graphs, and this paper examines how to adapt to this setting two approaches developed to study limits of dense graphs. We first consider flag algebras, which were used to open various questions on graphs to mechanical solving via semidefinite programming. We define flag algebras of order types, and use them to obtain, via the semidefinite method, new lower bounds on the density of 5- or 6-tuples in convex position in arbitrary point sets, as well as some inequalities expressing the difficulty of sampling order types uniformly. We next consider graphons, a representation of limits of dense graphs that enable their study by continuous probabilistic or analytic methods. We investigate how planar measures fare as a candidate analogue of graphons for limits of order types. We show that the map sending a measure to its associated limit is continuous and, if restricted to uniform measures on compact convex sets, a homeomorphism. We prove, however, that this map is not surjective. Finally, we examine a limit of order types similar to classical constructions in combinatorial geometry (Erdos-Szekeres, Horton...) and show that it cannot be represented by any somewhere regular measure; we analyze this example via an analogue of Sylvester's problem on the probability that k random points are in convex position.
Cite as

Xavier Goaoc, Alfredo Hubard, Rémi de Joannis de Verclos, Jean-Sébastien Sereni, and Jan Volec. Limits of Order Types. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 300-314, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{goaoc_et_al:LIPIcs.SOCG.2015.300,
  author =	{Goaoc, Xavier and Hubard, Alfredo and de Joannis de Verclos, R\'{e}mi and Sereni, Jean-S\'{e}bastien and Volec, Jan},
  title =	{{Limits of Order Types}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{300--314},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.300},
  URN =		{urn:nbn:de:0030-drops-51264},
  doi =		{10.4230/LIPIcs.SOCG.2015.300},
  annote =	{Keywords: order types, Limits of discrete structures, Flag algebras, Erdos-Szekeres, Sylvester’s problem}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.599
Realization Spaces of Arrangements of Convex Bodies

Authors: Michael Gene Dobbins, Andreas Holmsen, and Alfredo Hubard

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
We introduce combinatorial types of arrangements of convex bodies, extending order types of point sets to arrangements of convex bodies, and study their realization spaces. Our main results witness a trade-off between the combinatorial complexity of the bodies and the topological complexity of their realization space. On one hand, we show that every combinatorial type can be realized by an arrangement of convex bodies and (under mild assumptions) its realization space is contractible. On the other hand, we prove a universality theorem that says that the restriction of the realization space to arrangements of convex polygons with a bounded number of vertices can have the homotopy type of any primary semialgebraic set.
Cite as

Michael Gene Dobbins, Andreas Holmsen, and Alfredo Hubard. Realization Spaces of Arrangements of Convex Bodies. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 599-614, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{dobbins_et_al:LIPIcs.SOCG.2015.599,
  author =	{Dobbins, Michael Gene and Holmsen, Andreas and Hubard, Alfredo},
  title =	{{Realization Spaces of Arrangements of Convex Bodies}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{599--614},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.599},
  URN =		{urn:nbn:de:0030-drops-51020},
  doi =		{10.4230/LIPIcs.SOCG.2015.599},
  annote =	{Keywords: Oriented matroids, Convex sets, Realization spaces, Mnev’s universality theorem}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact