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

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Augmenting Plane Straight-Line Graphs to Meet Parity Constraints

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

摘要

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