Augmenting Plane Straight-Line Graphs to Meet Parity Constraints
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912232138342400 |
|---|---|
| author | Christiansen, Aleksander Bjørn Grodt Kleist, Linda Parada, Irene Rotenberg, Eva |
| author_facet | Christiansen, Aleksander Bjørn Grodt Kleist, Linda Parada, Irene Rotenberg, Eva |
| contents | Given a plane geometric graph $G$ on $n$ vertices, we want to augment it so that given parity constraints of the vertex degrees are met. In other words, given a subset $R$ of the vertices, we are interested in a plane geometric supergraph $G'$ such that exactly the vertices of $R$ have odd degree in $G'\setminus G$. We show that the question whether such a supergraph exists can be decided in polynomial time for two interesting cases. First, when the vertices are in convex position, we present a linear-time algorithm. Building on this insight, we solve the case when $G$ is a plane geometric path in $O(n \log n)$ time. This solves an open problem posed by Catana, Olaverri, Tejel, and Urrutia (Appl. Math. Comput. 2020). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_10066 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Augmenting Plane Straight-Line Graphs to Meet Parity Constraints Christiansen, Aleksander Bjørn Grodt Kleist, Linda Parada, Irene Rotenberg, Eva Computational Geometry Given a plane geometric graph $G$ on $n$ vertices, we want to augment it so that given parity constraints of the vertex degrees are met. In other words, given a subset $R$ of the vertices, we are interested in a plane geometric supergraph $G'$ such that exactly the vertices of $R$ have odd degree in $G'\setminus G$. We show that the question whether such a supergraph exists can be decided in polynomial time for two interesting cases. First, when the vertices are in convex position, we present a linear-time algorithm. Building on this insight, we solve the case when $G$ is a plane geometric path in $O(n \log n)$ time. This solves an open problem posed by Catana, Olaverri, Tejel, and Urrutia (Appl. Math. Comput. 2020). |
| title | Augmenting Plane Straight-Line Graphs to Meet Parity Constraints |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2502.10066 |