Search Results

Documents authored by Dorfer, Joseph


Document
Point Set Embeddability with List Constraints

Authors: Thomas Depian, Joseph Dorfer, Boris Klemz, Matthias Pfretzschner, and Lena Schlipf

Published in: LIPIcs, Volume 396, 34th International Symposium on Graph Drawing and Network Visualization (GD 2026)


Abstract
Deciding whether a given graph admits a planar straight-line drawing where each vertex is placed on some point from a given finite point set is known as Point Set Embeddability and is a classical problem in graph drawing. In this paper, we study the more general embeddability question where the placement of each vertex v is restricted to a list L(v) of admissible points. We first study the case where the given point set is in convex position. We show that this case is NP-hard even if the given graph is a matching and bi-labeled, i.e., each vertex has at most 2 admissible points. On the positive side, we present two efficient algorithms for the case where the given graph G is connected (and not necessarily bi-labeled): if G is equipped with a combinatorial embedding that needs to be respected, we can solve the problem in polynomial time; otherwise we can solve it in FPT-time with regard to the maximum vertex degree. In particular, this answers an open question by Frati, Glisse, Lenhart, Liotta, Mchedlidze, and Nishat [GD'13]. We then turn our attention to the more general case where the given point set is not necessarily in convex position. Here, we show NP-hardness for bi-labeled paths; notably these graphs have a unique combinatorial embedding and maximum degree two, thereby creating a stark contrast to our algorithms for the convex case. We also present an FPT-algorithm with respect to the vertex cover number for the special case of bi-labeled graphs. We complement this latter result by establishing paraNP-hardness in the tri-labeled setting for vertex cover number 2 and polynomial-time solvability for vertex cover number 1 and arbitrary L. Finally, we study optimization and extension variants, where we want to maximize the number of edges or extend a partial drawing, respectively. For the former, we show APX-hardness and for the latter, we provide a parameterized complexity dichotomy under natural extension parameters.

Cite as

Thomas Depian, Joseph Dorfer, Boris Klemz, Matthias Pfretzschner, and Lena Schlipf. Point Set Embeddability with List Constraints. In 34th International Symposium on Graph Drawing and Network Visualization (GD 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 396, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@InProceedings{depian_et_al:LIPIcs.GD.2026.35,
  author =	{Depian, Thomas and Dorfer, Joseph and Klemz, Boris and Pfretzschner, Matthias and Schlipf, Lena},
  title =	{{Point Set Embeddability with List Constraints}},
  booktitle =	{34th International Symposium on Graph Drawing and Network Visualization (GD 2026)},
  pages =	{35:1--35:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-452-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{396},
  editor =	{L\"{o}ffler, Maarten and Miksch, Silvia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2026.35},
  URN =		{urn:nbn:de:0030-drops-279308},
  doi =		{10.4230/LIPIcs.GD.2026.35},
  annote =	{Keywords: Point set embedding, List constraints, Parameterized algorithms and complexity, NP-hardness, Dynamic programming, Graph drawing, Computational geometry}
}
Document
Structural Properties of Shortest Flip Sequences Between Plane Spanning Trees

Authors: Oswin Aichholzer, Joseph Dorfer, Peter Kramer, Christian Rieck, and Birgit Vogtenhuber

Published in: LIPIcs, Volume 396, 34th International Symposium on Graph Drawing and Network Visualization (GD 2026)


Abstract
We study the problem of reconfiguring plane spanning trees on point sets in the plane in convex position. A flip is a reconfiguration step in which one edge of a tree is replaced with another, yielding again a plane spanning tree. For a given point set P, the flip graph has a vertex for each plane spanning tree on P, and an edge between any two trees that differ by a single flip. The flip distance between two trees is the length of a shortest path between them in the flip graph, that is, the minimum number of flips needed to transform one tree into the other. We study structural properties of shortest flip sequences. Over the years, several conjectures have been proposed regarding these sequences. The folklore happy edge conjecture suggests that any edge shared by both the initial and target tree is never flipped in a shortest flip sequence. Moreover, the parking conjecture claims that in shortest flip sequences, every edge is either flipped to a target edge or parked on the convex hull. Notably, the happy edge conjecture is implied by the parking conjecture. Furthermore, it has been conjectured that an edge is never reparked, that is, any edge resulting from a flip either is a target edge or is subsequently flipped to a target edge. Essentially, all recent flip algorithms rely on these three conjectures and the properties they imply. In this paper, we disprove both the parking and the reparking conjecture. In particular, we show that a flip sequence obeying the parking property sometimes needs linearly more flips than a shortest flip sequence, and exhibit examples where any shortest flip sequence flips some edge multiple times. In contrast, we identify several conditions under which the parking and reparking properties hold; these imply that the reparking property holds for compatible flips, and may be exploited by algorithms to obtain short flip sequences, especially for the compatible case.

Cite as

Oswin Aichholzer, Joseph Dorfer, Peter Kramer, Christian Rieck, and Birgit Vogtenhuber. Structural Properties of Shortest Flip Sequences Between Plane Spanning Trees. In 34th International Symposium on Graph Drawing and Network Visualization (GD 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 396, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.GD.2026.37,
  author =	{Aichholzer, Oswin and Dorfer, Joseph and Kramer, Peter and Rieck, Christian and Vogtenhuber, Birgit},
  title =	{{Structural Properties of Shortest Flip Sequences Between Plane Spanning Trees}},
  booktitle =	{34th International Symposium on Graph Drawing and Network Visualization (GD 2026)},
  pages =	{37:1--37:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-452-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{396},
  editor =	{L\"{o}ffler, Maarten and Miksch, Silvia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2026.37},
  URN =		{urn:nbn:de:0030-drops-279323},
  doi =		{10.4230/LIPIcs.GD.2026.37},
  annote =	{Keywords: Spanning trees, convex position, non-crossing, flip graph, happy edges, parking conjecture}
}
Document
Sliding Cubes in Parallel

Authors: Hugo A. Akitaya, Joseph Dorfer, Peter Kramer, Christian Rieck, Gabriel Shahrouzi, and Frederick Stock

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)


Abstract
In the classic sliding cube model for programmable matter in three dimensions, the task is to find a reconfiguration sequence between two connected configurations of n indistinguishable unit cube modules by sliding modules along their neighbors' faces. Depending on the objective, this sequence should minimize either the total energy expended (the number of moves) or the total elapsed time (the makespan). We give a number of results for the three-dimensional setting, including (i) the first algorithm that achieves worst-case optimal makespan under parallel motion in three dimensions, (ii) a proof of log-APX-hardness to decide either the optimal makespan or the optimal number of moves, which is the strongest known inapproximability bound in any related model, and (iii) a proof of NP-hardness to decide the optimal makespan under parallel motion, even if the two configurations differ only by one module and the optimal makespan is at most two. Our results strengthen the inapproximability claim from [Hugo A. Akitaya et al., 2022] and answer a question of [Akitaya et al., 2025] in the negative.

Cite as

Hugo A. Akitaya, Joseph Dorfer, Peter Kramer, Christian Rieck, Gabriel Shahrouzi, and Frederick Stock. Sliding Cubes in Parallel. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.ESA.2026.26,
  author =	{A. Akitaya, Hugo and Dorfer, Joseph and Kramer, Peter and Rieck, Christian and Shahrouzi, Gabriel and Stock, Frederick},
  title =	{{Sliding Cubes in Parallel}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{26:1--26:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.26},
  URN =		{urn:nbn:de:0030-drops-271621},
  doi =		{10.4230/LIPIcs.ESA.2026.26},
  annote =	{Keywords: Sliding squares, parallel motion, reconfigurability, three dimensions, constant makespan, log-APX-hardness, NP-hardness, worst-case optimality}
}
Document
Flip Distance of Non-Crossing Spanning Trees: NP-Hardness and Improved Bounds

Authors: Håvard Bakke Bjerkevik, Joseph Dorfer, Linda Kleist, Torsten Ueckerdt, and Birgit Vogtenhuber

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)


Abstract
We consider the problem of reconfiguring non-crossing spanning trees on point sets. For a set P of n points in general position in the plane, the flip graph ℱ(P) has a vertex for each non-crossing spanning tree on P and an edge between any two spanning trees that can be transformed into each other by the exchange of a single edge (coined a flip). This flip graph has been intensively studied, lately with an emphasis on determining its diameter diam(ℱ(P)) for sets P of n points in convex position. For this case, the current best bounds are 14/9⋅n - O(1) ≤ diam(ℱ(P)) < 15/9⋅n - 3, obtained in a recent breakthrough work [Bjerkevik, Kleist, Ueckerdt, and Vogtenhuber; SODA 2025]. The crucial tool for both the upper and lower bound are so-called conflict graphs, which the authors stated might be the key ingredient for determining the diameter (up to lower-order terms). In this paper, we pick up the concept of conflict graphs from the above-mentioned work and show that this tool is even more versatile than previously hoped. As our first main result, we use conflict graphs to show that computing the flip distance between two non-crossing spanning trees is NP-hard, even for point sets in convex position. Interestingly, the result still holds for more constrained flip operations, concretely, compatible flips (where the removed and the added edge do not cross) and rotations (where the removed and the added edge share an endpoint). Additionally, we present new insights on the diameter of the flip graph, by this directly extending the line of research from [BKUV SODA25]. Their lower bound is based on a constant-size pair of trees, one of which is of a type we refer to as stacked. We show that if one of the trees is stacked, then the lower bound is indeed optimal up to a constant term, that is, there exists a flip sequence of length at most 14/9⋅(n-1) to any other tree. Lastly, we improve the lower bound on the diameter of the flip graph ℱ(P) for n points in convex position to 11/7⋅n-o(n).

Cite as

Håvard Bakke Bjerkevik, Joseph Dorfer, Linda Kleist, Torsten Ueckerdt, and Birgit Vogtenhuber. Flip Distance of Non-Crossing Spanning Trees: NP-Hardness and Improved Bounds. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@InProceedings{bjerkevik_et_al:LIPIcs.SoCG.2026.16,
  author =	{Bjerkevik, H\r{a}vard Bakke and Dorfer, Joseph and Kleist, Linda and Ueckerdt, Torsten and Vogtenhuber, Birgit},
  title =	{{Flip Distance of Non-Crossing Spanning Trees: NP-Hardness and Improved Bounds}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.16},
  URN =		{urn:nbn:de:0030-drops-258225},
  doi =		{10.4230/LIPIcs.SoCG.2026.16},
  annote =	{Keywords: Non-crossing, spanning tree, plane graph, flip graph, reconfiguration, diameter, complexity, NP-hard, edge exchange, compatible flip, rotation, happy edge property}
}
Document
Media Exposition
Sliding Cubes in Parallel (Media Exposition)

Authors: Hugo A. Akitaya, Joseph Dorfer, Peter Kramer, Christian Rieck, Soham Samanta, Gabriel Shahrouzi, and Frederick Stock

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)


Abstract
The sliding cubes model serves as a well-established theoretical framework for formalizing and analyzing reconfiguration algorithms in modular robotic systems built from face-connected cubic modules. We extend the parallel sliding cubes model from two to three dimensions, presenting new algorithms, surprising complexity results, and a generalization of the best known bounds from two to three dimensions. A companion video visualizes and explains our results.

Cite as

Hugo A. Akitaya, Joseph Dorfer, Peter Kramer, Christian Rieck, Soham Samanta, Gabriel Shahrouzi, and Frederick Stock. Sliding Cubes in Parallel (Media Exposition). In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 96:1-96:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.SoCG.2026.96,
  author =	{A. Akitaya, Hugo and Dorfer, Joseph and Kramer, Peter and Rieck, Christian and Samanta, Soham and Shahrouzi, Gabriel and Stock, Frederick},
  title =	{{Sliding Cubes in Parallel}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{96:1--96:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.96},
  URN =		{urn:nbn:de:0030-drops-259020},
  doi =		{10.4230/LIPIcs.SoCG.2026.96},
  annote =	{Keywords: Sliding squares, parallel motion, reconfigurability, three dimensions, constant makespan, log-APX hardness, NP-hardness, worst-case optimality}
}
Document
Higher Hardness Results for the Reconfiguration of Odd Matchings

Authors: Joseph Dorfer

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


Abstract
We study the reconfiguration of odd matchings of combinatorial graphs. Odd matchings are matchings that cover all but one vertex of a graph. A reconfiguration step, or flip, is an operation that matches the isolated vertex and, consequently, isolates another vertex. The flip graph of odd matchings is a graph that has all odd matchings of a graph as vertices and an edge between two vertices if their corresponding matchings can be transformed into one another via a single flip. We show that computing the diameter of the flip graph of odd matchings is Π₂^p-hard. This complements a recent result by Wulf [FOCS25] that it is Π₂^p-hard to compute the diameter of the flip graph of perfect matchings where a flip swaps matching edges along a single cycle of unbounded size. Further, we show that computing the radius of the flip graph of odd matchings is Σ₃^p-hard. The respective decision problems for the diameter and the radius are also complete in the respective level of the polynomial hierarchy. This shows that computing the radius of the flip graph of odd matchings is provably harder than computing its diameter, unless the polynomial hierarchy collapses. Finally, we reduce set cover to the problem of finding shortest flip sequences. As a consequence, we show APX-hardness and that the problem cannot be approximated by a sublogarithmic factor. By doing so, we answer a question asked by Aichholzer, Brenner, Dorfer, Hoang, Perz, Rieck, and Verciani [GD25].

Cite as

Joseph Dorfer. Higher Hardness Results for the Reconfiguration of Odd Matchings. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@InProceedings{dorfer:LIPIcs.STACS.2026.33,
  author =	{Dorfer, Joseph},
  title =	{{Higher Hardness Results for the Reconfiguration of Odd Matchings}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{33:1--33:16},
  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.33},
  URN =		{urn:nbn:de:0030-drops-255222},
  doi =		{10.4230/LIPIcs.STACS.2026.33},
  annote =	{Keywords: Graph Reconfiguration Problems, Flip Graphs, Polynomial Hierarchy, APX-hardness}
}
Document
Constrained Flips in Plane Spanning Trees

Authors: Oswin Aichholzer, Joseph Dorfer, and Birgit Vogtenhuber

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)


Abstract
A flip in a plane spanning tree T is the operation of removing one edge from T and adding another edge such that the resulting structure is again a plane spanning tree. For trees on a set of points in convex position we study two classic types of constrained flips: (1) Compatible flips are flips in which the removed and inserted edge do not cross each other. We relevantly improve the previous upper bound of 2n-O(√n) on the diameter of the compatible flip graph to (5n/3)-O(1), by this matching the upper bound for unrestricted flips by Bjerkevik, Kleist, Ueckerdt, and Vogtenhuber [SODA 2025] up to an additive constant of 1. We further show that no shortest compatible flip sequence removes an edge that is already in its target position. Using this so-called happy edge property, we derive a fixed-parameter tractable algorithm to compute the shortest compatible flip sequence between two given trees. (2) Rotations are flips in which the removed and inserted edge share a common vertex. Besides showing that the happy edge property does not hold for rotations, we improve the previous upper bound of 2n-O(1) for the diameter of the rotation graph to (7n/4)-O(1).

Cite as

Oswin Aichholzer, Joseph Dorfer, and Birgit Vogtenhuber. Constrained Flips in Plane Spanning Trees. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)


Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.GD.2025.5,
  author =	{Aichholzer, Oswin and Dorfer, Joseph and Vogtenhuber, Birgit},
  title =	{{Constrained Flips in Plane Spanning Trees}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{5:1--5:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.5},
  URN =		{urn:nbn:de:0030-drops-249913},
  doi =		{10.4230/LIPIcs.GD.2025.5},
  annote =	{Keywords: Non-crossing spanning trees, Flip Graphs, Diameter, Complexity, Happy edges}
}
Document
Flipping Odd Matchings in Geometric and Combinatorial Settings

Authors: Oswin Aichholzer, Sofia Brenner, Joseph Dorfer, Hung P. Hoang, Daniel Perz, Christian Rieck, and Francesco Verciani

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)


Abstract
We study the problem of reconfiguring odd matchings, that is, matchings that cover all but a single vertex. Our reconfiguration operation is a so-called flip where the unmatched vertex of the first matching gets matched, while consequently another vertex becomes unmatched. We consider two distinct settings: the geometric setting, in which the vertices are points embedded in the plane and all occurring odd matchings are crossing-free, and a combinatorial setting, in which we consider odd matchings in general graphs. For the latter setting, we provide a complete polynomial time checkable characterization of graphs in which any two odd matchings can be reconfigured into each another. This complements the previously known result that the flip graph is always connected in the geometric setting [Oswin Aichholzer et al., 2025]. In the combinatorial setting, we prove that the diameter of the flip graph, if connected, is linear in the number of vertices. Furthermore, we establish that deciding whether there exists a flip sequence of length k transforming one given matching into another is NP-complete in both the combinatorial and the geometric settings. To prove the latter, we introduce a framework that allows us to transform partial order types into general position with only polynomial overhead. Finally, we demonstrate that when parameterized by the flip distance k, the problem is fixed-parameter tractable (FPT) in the geometric setting when restricted to convex point sets.

Cite as

Oswin Aichholzer, Sofia Brenner, Joseph Dorfer, Hung P. Hoang, Daniel Perz, Christian Rieck, and Francesco Verciani. Flipping Odd Matchings in Geometric and Combinatorial Settings. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)


Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.GD.2025.12,
  author =	{Aichholzer, Oswin and Brenner, Sofia and Dorfer, Joseph and Hoang, Hung P. and Perz, Daniel and Rieck, Christian and Verciani, Francesco},
  title =	{{Flipping Odd Matchings in Geometric and Combinatorial Settings}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{12:1--12:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.12},
  URN =		{urn:nbn:de:0030-drops-249983},
  doi =		{10.4230/LIPIcs.GD.2025.12},
  annote =	{Keywords: Odd matchings, reconfiguration, flip graph, geometric, combinatorial, connectivity, NP-hardness, FPT}
}

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