TY - GEN
T1 - Augmenting Plane Straight-Line Graphs to Meet Parity Constraints.
AU - Christiansen, Aleksander Bjørn Grodt
AU - Kleist, Linda
AU - Parada, Irene
AU - Rotenberg, Eva
N1 - DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.
PY - 2025/2/14
Y1 - 2025/2/14
N2 - 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′ \ 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).
AB - 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′ \ 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).
KW - Plane geometric graphs
KW - Augmentation problems
KW - Parity constraints
KW - Geometric paths
KW - Convex geometric graphs
U2 - 10.48550/ARXIV.2502.10066
DO - 10.48550/ARXIV.2502.10066
M3 - Article in proceedings
VL - abs/2502.10066
BT - Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Gozd Martuljek, Slovenia, June 19-21, 2024, Revised Selected Papers
ER -