Veröffentlichung

Titel:

Augmenting Geometric Graphs with Matchings

AutorInnen:

Alexander Pilz
Jonathan Rollin
Lena Schlipf
André Schulz

Kategorie:

Konferenzbandbeiträge

erschienen in:

Graph Drawing and Network Visualization, 28th International Symposium, GD 2020, Vancouver, BC, Canada, pp. 490-504, September 16–18, 2020

Abstract:

We study noncrossing geometric graphs and their disjoint compatible geometric matchings. Given a cycle (a polygon) P we want to draw a set of pairwise disjoint straight-line edges with endpoints on the vertices of P so that these new edges neither cross nor contain any edge of the polygon. We prove NP-completeness of deciding whether there is such a perfect matching. For any n-vertex polygon, with 𝑛≥4 , we show that such a matching with <𝑛/7 edges is not maximal, that is, it can be extended by another compatible matching edge. We also construct polygons with maximal compatible matchings with n/7 edges, demonstrating the tightness of this bound. Tight bounds on the size of a minimal maximal compatible matching are also obtained for the families of d-regular geometric graphs for each 𝑑∈{0,1,2} . Finally we consider a related problem. We prove that it is NP-complete to decide whether a noncrossing geometric graph G admits a set of compatible noncrossing edges such that G together with these edges has minimum degree five .

Download:

Springer

BibTeX-Eintrag:

@inproceedings{DBLP:conf/gd/PilzRS020, author = {Alexander Pilz and Jonathan Rollin and Lena Schlipf and Andr{\'{e}} Schulz}, editor = {David Auber and Pavel Valtr}, title = {Augmenting Geometric Graphs with Matchings}, booktitle = {Graph Drawing and Network Visualization - 28th International Symposium, {GD} 2020, Vancouver, BC, Canada, September 16-18, 2020, Revised Selected Papers}, series = {Lecture Notes in Computer Science}, volume = {12590}, pages = {490--504}, publisher = {Springer}, year = {2020}, url = {https://doi.org/10.1007/978-3-030-68766-3\_38}, doi = {10.1007/978-3-030-68766-3\_38}, timestamp = {Tue, 02 Mar 2021 11:26:33 +0100}, biburl = {https://dblp.org/rec/conf/gd/PilzRS020.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }