Augmenting Plane Straight-Line Graphs to Meet Parity Constraints.

Aleksander Bjørn Grodt Christiansen; Linda Kleist; Irene Parada; Eva Rotenberg

doi:10.48550/ARXIV.2502.10066

Augmenting Plane Straight-Line Graphs to Meet Parity Constraints.

Aleksander Bjørn Grodt Christiansen
, Linda Kleist
, Irene Parada
, Eva Rotenberg

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Abstract

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).

Original language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Gozd Martuljek, Slovenia, June 19-21, 2024, Revised Selected Papers
Volume	abs/2502.10066
Publication date	14 Feb 2025
DOIs	https://doi.org/10.48550/ARXIV.2502.10066
Publication status	Published - 14 Feb 2025
Externally published	Yes
Event	Graph-Theoretic Concepts in Computer Science - Gozd Martuljek, Slovenia Duration: 19 Jun 2024 → 21 Jun 2024 Conference number: 50th

Workshop

Workshop	Graph-Theoretic Concepts in Computer Science
Number	50th
Country/Territory	Slovenia
City	Gozd Martuljek
Period	19/06/2024 → 21/06/2024

Keywords

Plane geometric graphs
Augmentation problems
Parity constraints
Geometric paths
Convex geometric graphs

Access to Document

10.48550/ARXIV.2502.10066Licence: CC BY-NC-SA

https://dblp.org/rec/journals/corr/abs-2502-10066

ERCP: Efficient Recomputation for Changeful Problems
Rotenberg, E. (PI), Berg, S. D. (Collaborator) & Hoog, I. V. D. (Collaborator)
Villum Foundation
01/07/2021 → 30/06/2026
Project: Research

Cite this

@inproceedings{93bf5452f9f146088eb5d5e597c2ec6c,

title = "Augmenting Plane Straight-Line Graphs to Meet Parity Constraints.",

abstract = "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′ \textbackslash{} 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). ",

keywords = "Plane geometric graphs, Augmentation problems, Parity constraints, Geometric paths, Convex geometric graphs",

author = "Christiansen, \{Aleksander Bj{\o}rn Grodt\} and Linda Kleist and Irene Parada and Eva Rotenberg",

note = "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.; Graph-Theoretic Concepts in Computer Science ; Conference date: 19-06-2024 Through 21-06-2024",

year = "2025",

month = feb,

day = "14",

doi = "10.48550/ARXIV.2502.10066",

language = "English",

volume = "abs/2502.10066",

booktitle = "Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Gozd Martuljek, Slovenia, June 19-21, 2024, Revised Selected Papers",

}

Christiansen, ABG, Kleist, L, Parada, I & Rotenberg, E 2025, Augmenting Plane Straight-Line Graphs to Meet Parity Constraints. in Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Gozd Martuljek, Slovenia, June 19-21, 2024, Revised Selected Papers. vol. abs/2502.10066, Graph-Theoretic Concepts in Computer Science, Gozd Martuljek, Slovenia, 19/06/2024. https://doi.org/10.48550/ARXIV.2502.10066

Augmenting Plane Straight-Line Graphs to Meet Parity Constraints. / Christiansen, Aleksander Bjørn Grodt; Kleist, Linda; Parada, Irene et al.
Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Gozd Martuljek, Slovenia, June 19-21, 2024, Revised Selected Papers. Vol. abs/2502.10066 2025.

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

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 - Conference code: 50th

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

T2 - Graph-Theoretic Concepts in Computer Science

Y2 - 19 June 2024 through 21 June 2024

ER -

Augmenting Plane Straight-Line Graphs to Meet Parity Constraints.

Abstract

Workshop

Keywords

Access to Document

Fingerprint

Projects

ERCP: Efficient Recomputation for Changeful Problems

Cite this