Plane augmentation of plane graphs to meet parity constraints

DOI10.1016/J.AMC.2020.125513MaRDI QIDQ2656724zbMATH OpenOpenAlexFDO

Authors J. C. Catana, J. Urrutia, Alfredo García, Javier Tejel

Publication date 16 March 2021

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.11863

zbMATH Keywords

\( \mathcal{NP} \)-complete problemsaugmentation problemsmaximal outerplane graphsparity constraintsplane geometric graphsplane topological graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Abstract: A plane topological graph $G=(V,E)$ is a graph drawn in the plane whose vertices are points in the plane and whose edges are simple curves that do not intersect, except at their endpoints. Given a plane topological graph $G=(V,E)$ and a set $C_G$ of parity constraints, in which every vertex has assigned a parity constraint on its degree, either even or odd, we say that $G$ is emph{topologically augmentable} to meet $C_G$ if there exits a plane topological graph $H$ on the same set of vertices, such that $G$ and $H$ are edge-disjoint and their union is a plane topological graph that meets all parity constraints. In this paper, we prove that the problem of deciding if a plane topological graph is topologically augmentable to meet parity constraints is $mathcalNP$-complete, even if the set of vertices that must change their parities is $V$ or the set of vertices with odd degree. In particular, deciding if a plane topological graph can be augmented to a Eulerian plane topological graph is $mathcalNP$-complete. Analogous complexity results are obtained, when the augmentation must be done by a plane topological perfect matching between the vertices not meeting their parities. We extend these hardness results to planar graphs, when the augmented graph must be planar, and to plane geometric graphs (plane topological graphs whose edges are straight-line segments). In addition, when it is required that the augmentation is made by a plane geometric perfect matching between the vertices not meeting their parities, we also prove that this augmentation problem is $mathcalNP$-complete for plane geometric trees and paths. For the particular family of maximal outerplane graphs, we characterize maximal outerplane graphs that are topological augmentable to satisfy a set of parity constraints.

Recommendations

• Plane graphs with parity constraints
• Plane Graphs with Parity Constraints
• Regular augmentation of planar graphs
• scientific article; zbMATH DE number 177556
• Cubic augmentation of planar graphs

Cites work

• A simplified 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• Augmentation Problems
• Augmenting the connectivity of geometric graphs
• Augmenting the connectivity of planar and geometric graphs
• Augmenting the edge connectivity of planar straight line graphs to three
• Augmenting undirected node-connectivity by one
• Bounded length, 2-edge augmentation of geometric planar graphs
• Compatible geometric matchings
• Compatible spanning trees
• Connections in combinatorial optimization
• Connectivity augmentation in planar straight line graphs
• Disjoint compatible geometric matchings
• Editing to Eulerian graphs
• Efficient algorithms for Eulerian extension and rural Postman
• Euler index in uncertain graph
• Geometric biplane graphs. II: Graph augmentation
• How to Draw a Graph
• scientific article; zbMATH DE number 177556 (Why is no real title available?)
• Linear transformation distance for bichromatic matchings
• Matching, Euler tours and the Chinese postman
• Minimum block containing a given graph
• Minimum weight connectivity augmentation for planar straight-line graphs
• Parameterized complexity of Eulerian deletion problems
• Parameterized complexity of even/odd subgraph problems
• Parity-constrained triangulations with Steiner points
• Planar Formulae and Their Uses
• Plane geometric graph augmentation: a generic perspective
• Plane graphs with parity constraints
• Supereulerian digraphs with given diameter
• The spanning subgraphs of eulerian graphs

Cited in

(4)

• Plane graphs with parity constraints
• Plane Graphs with Parity Constraints
• On plane subgraphs of complete topological drawings
• Augmenting plane straight-line graphs to meet parity constraints

This page was built for publication: Plane augmentation of plane graphs to meet parity constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2656724)