5 Search Results for "Rollin, Jonathan"

Document
DOI: 10.4230/LIPIcs.STACS.2026.49
2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs

Authors: Rohit Gurjar, Kilian Rothmund, and Thomas Thierauf

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Minimally rigid graphs can be decided and embedded in the plane efficiently, i.e. in polynomial time. There is also an efficient randomized parallel algorithm, i.e. in RNC. We present an NC-algorithm to decide whether one-crossing-minor-free graphs are minimally rigid. In the special case of K_{3,3}-free graphs, we also compute an infinitesimally rigid embedding in NC.
Cite as

Rohit Gurjar, Kilian Rothmund, and Thomas Thierauf. 2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 49:1-49:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gurjar_et_al:LIPIcs.STACS.2026.49,
  author =	{Gurjar, Rohit and Rothmund, Kilian and Thierauf, Thomas},
  title =	{{2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{49:1--49:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.49},
  URN =		{urn:nbn:de:0030-drops-255385},
  doi =		{10.4230/LIPIcs.STACS.2026.49},
  annote =	{Keywords: Graph Rigidity, Parallel Algorithms, Polynomial Identity Testing, Derandomization}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.15
A Polynomial-Time Approximation Algorithm for Complete Interval Minors

Authors: Romain Bourneuf, Julien Cocquet, Chaoliang Tang, and Stéphan Thomassé

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
As shown by Robertson and Seymour, deciding whether the complete graph K_t is a minor of an input graph G is a fixed parameter tractable problem when parameterized by t. From the approximation viewpoint, a substantial gap remains: there is no PTAS for finding the largest complete minor unless P = NP, whereas the best known result is a polytime O(√ n)-approximation algorithm by Alon, Lingas and Wahlén. We investigate the complexity of finding K_t as interval minor in ordered graphs (i.e. graphs with a linear order on the vertices, in which intervals are contracted to form minors). Our main result is a polytime f(t)-approximation algorithm, where f is triply exponential in t but independent of n. The algorithm is based on delayed decompositions and shows that ordered graphs without a K_t interval minor can be constructed via a bounded number of three operations: closure under substitutions, edge union, and concatenation of a stable set. As a byproduct, graphs avoiding K_t as an interval minor have bounded chromatic number.
Cite as

Romain Bourneuf, Julien Cocquet, Chaoliang Tang, and Stéphan Thomassé. A Polynomial-Time Approximation Algorithm for Complete Interval Minors. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 15:1-15:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bourneuf_et_al:LIPIcs.APPROX/RANDOM.2025.15,
  author =	{Bourneuf, Romain and Cocquet, Julien and Tang, Chaoliang and Thomass\'{e}, St\'{e}phan},
  title =	{{A Polynomial-Time Approximation Algorithm for Complete Interval Minors}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{15:1--15:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.15},
  URN =		{urn:nbn:de:0030-drops-243814},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.15},
  annote =	{Keywords: Approximation algorithm, Ordered graphs, Interval minors, Delayed decompositions}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.11
Crossing and Independent Families Among Polygons

Authors: Anna Brötzner, Robert Ganian, Thekla Hamm, Fabian Klute, and Irene Parada

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
Given a set A of points in the plane, a family of line segments forming a matching in A is called crossing (or independent) if each pair of segments in the family intersects (or is non-intersecting, respectively). In past works, these notions have been generalized to polygons by identifying the points in A with the vertices of a given set of polygons and forbidding the line segments from intersecting or overlapping with polygon walls. In this work, we study the computational complexity of computing maximum crossing and independent families in this more general setting. As our first two results, we show that both problems are NP-hard already when the polygons are triangles. Motivated by this, we turn to parameterized algorithms. For our main algorithmic results, we consider the number of polygons on the input as the natural parameter and under this parameterization obtain a fixed-parameter algorithm for computing a largest crossing family among these polygons, and a separate XP-algorithm for computing a largest independent family that lies in one of the faces of the polygonal domain.
Cite as

Anna Brötzner, Robert Ganian, Thekla Hamm, Fabian Klute, and Irene Parada. Crossing and Independent Families Among Polygons. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{brotzner_et_al:LIPIcs.WADS.2025.11,
  author =	{Br\"{o}tzner, Anna and Ganian, Robert and Hamm, Thekla and Klute, Fabian and Parada, Irene},
  title =	{{Crossing and Independent Families Among Polygons}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.11},
  URN =		{urn:nbn:de:0030-drops-242424},
  doi =		{10.4230/LIPIcs.WADS.2025.11},
  annote =	{Keywords: crossing families, crossing-free matchings, segment intersection graphs, computational geometry, parameterized algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.44
On the Geometric Thickness of 2-Degenerate Graphs

Authors: Rahul Jain, Marco Ricci, Jonathan Rollin, and André Schulz

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

Abstract
A graph is 2-degenerate if every subgraph contains a vertex of degree at most 2. We show that every 2-degenerate graph can be drawn with straight lines such that the drawing decomposes into 4 plane forests. Therefore, the geometric arboricity, and hence the geometric thickness, of 2-degenerate graphs is at most 4. On the other hand, we show that there are 2-degenerate graphs that do not admit any straight-line drawing with a decomposition of the edge set into 2 plane graphs. That is, there are 2-degenerate graphs with geometric thickness, and hence geometric arboricity, at least 3. This answers two questions posed by Eppstein [Separating thickness from geometric thickness. In Towards a Theory of Geometric Graphs, vol. 342 of Contemp. Math., AMS, 2004].
Cite as

Rahul Jain, Marco Ricci, Jonathan Rollin, and André Schulz. On the Geometric Thickness of 2-Degenerate Graphs. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jain_et_al:LIPIcs.SoCG.2023.44,
  author =	{Jain, Rahul and Ricci, Marco and Rollin, Jonathan and Schulz, Andr\'{e}},
  title =	{{On the Geometric Thickness of 2-Degenerate Graphs}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{44:1--44: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.44},
  URN =		{urn:nbn:de:0030-drops-178946},
  doi =		{10.4230/LIPIcs.SoCG.2023.44},
  annote =	{Keywords: Degeneracy, geometric thickness, geometric arboricity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.79
Recognizing Planar Laman Graphs

Authors: Jonathan Rollin, Lena Schlipf, and André Schulz

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Laman graphs are the minimally rigid graphs in the plane. We present two algorithms for recognizing planar Laman graphs. A simple algorithm with running time O(n^(3/2)) and a more complicated algorithm with running time O(n log^3 n) based on involved planar network flow algorithms. Both improve upon the previously fastest algorithm for general graphs by Gabow and Westermann [Algorithmica, 7(5-6):465 - 497, 1992] with running time O(n sqrt{n log n}). To solve this problem we introduce two algorithms (with the running times stated above) that check whether for a directed planar graph G, disjoint sets S, T subseteq V(G), and a fixed k the following connectivity condition holds: for each vertex s in S there are k directed paths from s to T pairwise having only vertex s in common. This variant of connectivity seems interesting on its own.
Cite as

Jonathan Rollin, Lena Schlipf, and André Schulz. Recognizing Planar Laman Graphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 79:1-79:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{rollin_et_al:LIPIcs.ESA.2019.79,
  author =	{Rollin, Jonathan and Schlipf, Lena and Schulz, Andr\'{e}},
  title =	{{Recognizing Planar Laman Graphs}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{79:1--79:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.79},
  URN =		{urn:nbn:de:0030-drops-112001},
  doi =		{10.4230/LIPIcs.ESA.2019.79},
  annote =	{Keywords: planar graphs, Laman graphs, network flow, connectivity}
}
  • Refine by Type
  • 5 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 2 2025
  • 1 2023
  • 1 2019

  • Refine by Author
  • 2 Rollin, Jonathan
  • 2 Schulz, André
  • 1 Bourneuf, Romain
  • 1 Brötzner, Anna
  • 1 Cocquet, Julien
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs

  • Refine by Classification
  • 2 Mathematics of computing → Graph theory
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Graph algorithms analysis
  • Show More...

  • Refine by Keyword
  • 1 Approximation algorithm
  • 1 Degeneracy
  • 1 Delayed decompositions
  • 1 Derandomization
  • 1 Graph Rigidity
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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