3 Search Results for "Aleardi, Luca Castelli"

Document
DOI: 10.4230/LIPIcs.MFCS.2024.77
Toward Grünbaum’s Conjecture for 4-Connected Graphs

Authors: Christian Ortlieb

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Given a spanning tree T of a 3-connected planar graph G, the co-tree of T is the spanning tree of the dual graph G^* given by the duals of the edges that are not in T. Grünbaum conjectured in 1970 that there is such a spanning tree T such that T and its co-tree both have maximum degree at most 3. In 2014, Biedl proved that there is a spanning tree T such that T and its co-tree have maximum degree at most 5. Using structural insights into Schnyder woods, Schmidt and the author recently improved this bound on the maximum degree to 4. In this paper, we prove that in a 4-connected planar graph there exists a spanning tree T of maximum degree at most 3 such its co-tree has maximum degree at most 4. This almost solves Grünbaum’s conjecture for 4-connected graphs.
Cite as

Christian Ortlieb. Toward Grünbaum’s Conjecture for 4-Connected Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 77:1-77:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ortlieb:LIPIcs.MFCS.2024.77,
  author =	{Ortlieb, Christian},
  title =	{{Toward Gr\"{u}nbaum’s Conjecture for 4-Connected Graphs}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{77:1--77:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.77},
  URN =		{urn:nbn:de:0030-drops-206339},
  doi =		{10.4230/LIPIcs.MFCS.2024.77},
  annote =	{Keywords: 4-connected planar graph, spanning tree, maximum degree, Schnyder wood, Gr\"{u}nbaum}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.32
SCARST: Schnyder Compact and Regularity Sensitive Triangulation Data Structure

Authors: Luca Castelli Aleardi and Olivier Devillers

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
We consider the design of fast and compact representations of the connectivity information of triangle meshes. Although traditional data structures (Half-Edge, Corner Table) are fast and user-friendly, they tend to be memory-expensive. On the other hand, compression schemes, while meeting information-theoretic lower bounds, do not support navigation within the mesh structure. Compact representations provide an advantageous balance for representing large meshes, enabling a judicious compromise between memory consumption and fast implementation of navigational operations. We propose new representations that are sensitive to the regularity of the graph while still having worst case guarantees. For all our data structures we have both an interesting storage cost, typically 2 or 3 r.p.v. (references per vertex) in the case of very regular triangulations, and provable upper bounds in the worst case scenario. One of our solutions has a worst case cost of 3.33 r.p.v., which is currently the best-known bound improving the previous 4 r.p.v. [Castelli et al. 2018]. Our representations have slightly slower running times (factors 1.5 to 4) than classical data structures. In our experiments we compare on various meshes runtime and memory performance of our representations with those of the most efficient existing solutions.
Cite as

Luca Castelli Aleardi and Olivier Devillers. SCARST: Schnyder Compact and Regularity Sensitive Triangulation Data Structure. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 32:1-32:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{castellialeardi_et_al:LIPIcs.SoCG.2024.32,
  author =	{Castelli Aleardi, Luca and Devillers, Olivier},
  title =	{{SCARST: Schnyder Compact and Regularity Sensitive Triangulation Data Structure}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{32:1--32:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.32},
  URN =		{urn:nbn:de:0030-drops-199779},
  doi =		{10.4230/LIPIcs.SoCG.2024.32},
  annote =	{Keywords: Meshes, compression, triangulations, compact representations}
}
Document
DOI: 10.4230/LIPIcs.SEA.2018.24
Fast Spherical Drawing of Triangulations: An Experimental Study of Graph Drawing Tools

Authors: Luca Castelli Aleardi, Gaspard Denis, and Éric Fusy

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

Abstract
We consider the problem of computing a spherical crossing-free geodesic drawing of a planar graph: this problem, as well as the closely related spherical parameterization problem, has attracted a lot of attention in the last two decades both in theory and in practice, motivated by a number of applications ranging from texture mapping to mesh remeshing and morphing. Our main concern is to design and implement a linear time algorithm for the computation of spherical drawings provided with theoretical guarantees. While not being aesthetically pleasing, our method is extremely fast and can be used as initial placer for spherical iterative methods and spring embedders. We provide experimental comparison with initial placers based on planar Tutte parameterization. Finally we explore the use of spherical drawings as initial layouts for (Euclidean) spring embedders: experimental evidence shows that this greatly helps to untangle the layout and to reach better local minima.
Cite as

Luca Castelli Aleardi, Gaspard Denis, and Éric Fusy. Fast Spherical Drawing of Triangulations: An Experimental Study of Graph Drawing Tools. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{aleardi_et_al:LIPIcs.SEA.2018.24,
  author =	{Aleardi, Luca Castelli and Denis, Gaspard and Fusy, \'{E}ric},
  title =	{{Fast Spherical Drawing of Triangulations: An Experimental Study of Graph Drawing Tools}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{24:1--24:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.24},
  URN =		{urn:nbn:de:0030-drops-89597},
  doi =		{10.4230/LIPIcs.SEA.2018.24},
  annote =	{Keywords: Graph drawing, planar triangulations, spherical parameterizations}
}
  • Refine by Author
  • 1 Aleardi, Luca Castelli
  • 1 Castelli Aleardi, Luca
  • 1 Denis, Gaspard
  • 1 Devillers, Olivier
  • 1 Fusy, Éric
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Graph theory
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Theory of computation → Computational geometry

  • Refine by Keyword
  • 1 4-connected planar graph
  • 1 Graph drawing
  • 1 Grünbaum
  • 1 Meshes
  • 1 Schnyder wood
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2024
  • 1 2018

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