Search Results

Documents authored by Perz, Daniel

Document
DOI: 10.4230/LIPIcs.GD.2025.12
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}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.21
Nearest-Neighbor Decompositions of Drawings

Authors: Jonas Cleve, Nicolas Grelier, Kristin Knorr, Maarten Löffler, Wolfgang Mulzer, and Daniel Perz

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
Let 𝒟 be a set of straight-line segments in the plane, potentially crossing, and let c be a positive integer. We denote by P the union of the endpoints of the straight-line segments of 𝒟 and of the intersection points between pairs of segments. We say that 𝒟 has a nearest-neighbor decomposition into c parts if we can partition P into c point sets P₁, … , P_c such that 𝒟 is the union of the nearest neighbor graphs on P₁, … , P_c. We show that it is NP-complete to decide whether 𝒟 can be drawn as the union of c ≥ 3 nearest-neighbor graphs, even when no two segments cross. We show that for c = 2, it is NP-complete in the general setting and polynomial-time solvable when no two segments cross. We show the existence of an O(log n)-approximation algorithm running in subexponential time for partitioning 𝒟 into a minimum number of nearest-neighbor graphs. As a main tool in our analysis, we establish the notion of the conflict graph for a drawing 𝒟. The vertices of the conflict graph are the connected components of 𝒟, with the assumption that each connected component is the nearest neighbor graph of its vertices, and there is an edge between two components U and V if and only if the nearest neighbor graph of U ∪ V contains an edge between a vertex in U and a vertex in V. We show that string graphs are conflict graphs of certain planar drawings. For planar graphs and complete k-partite graphs, we give additional, more efficient constructions. We furthermore show that there are subdivisions of non-planar graphs that are not conflict graphs. Lastly, we show a separator lemma for conflict graphs.
Cite as

Jonas Cleve, Nicolas Grelier, Kristin Knorr, Maarten Löffler, Wolfgang Mulzer, and Daniel Perz. Nearest-Neighbor Decompositions of Drawings. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{cleve_et_al:LIPIcs.SWAT.2022.21,
  author =	{Cleve, Jonas and Grelier, Nicolas and Knorr, Kristin and L\"{o}ffler, Maarten and Mulzer, Wolfgang and Perz, Daniel},
  title =	{{Nearest-Neighbor Decompositions of Drawings}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{21:1--21:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.21},
  URN =		{urn:nbn:de:0030-drops-161812},
  doi =		{10.4230/LIPIcs.SWAT.2022.21},
  annote =	{Keywords: nearest-neighbors, decompositions, drawing}
}
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact