000106621 001__ 106621 000106621 005__ 20210902121824.0 000106621 0247_ $$2doi$$a10.1016/j.amc.2020.125513 000106621 0248_ $$2sideral$$a119084 000106621 037__ $$aART-2020-119084 000106621 041__ $$aeng 000106621 100__ $$aCatana, J.C. 000106621 245__ $$aPlane augmentation of plane graphs to meet parity constraints 000106621 260__ $$c2020 000106621 5060_ $$aAccess copy available to the general public$$fUnrestricted 000106621 5203_ $$aA 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 CG of parity constraints, in which every vertex has assigned a parity constraint on its degree, either even or odd, we say that G is topologically augmentable to meet CG if there exists a set E' of new edges, disjoint with E, such that G'=(V, E¿E') is noncrossing and 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 NP-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 NP-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 NP-complete for plane geometric 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. We also provide a polynomial time algorithm that decides if a maximal outerplane graph is topologically augmentable to meet parity constraints, and if so, produces a set of edges with minimum cardinality. 000106621 536__ $$9info:eu-repo/grantAgreement/ES/DGA-FEDER/E41-17R$$9info:eu-repo/grantAgreement/EC/H2020/734922/EU/Combinatorics of Networks and Computation/CONNECT$$9This project has received funding from the European Union’s Horizon 2020 research and innovation program under grant agreement No H2020 734922-CONNECT$$9info:eu-repo/grantAgreement/ES/MINECO-FEDER/MTM2015-63791-R 000106621 540__ $$9info:eu-repo/semantics/openAccess$$aby-nc-nd$$uhttp://creativecommons.org/licenses/by-nc-nd/3.0/es/ 000106621 590__ $$a4.091$$b2020 000106621 591__ $$aMATHEMATICS, APPLIED$$b7 / 265 = 0.026$$c2020$$dQ1$$eT1 000106621 592__ $$a0.971$$b2020 000106621 593__ $$aComputational Mathematics$$c2020$$dQ1 000106621 593__ $$aApplied Mathematics$$c2020$$dQ1 000106621 655_4 $$ainfo:eu-repo/semantics/article$$vinfo:eu-repo/semantics/acceptedVersion 000106621 700__ $$0(orcid)0000-0002-6519-1472$$aGarcía, A.$$uUniversidad de Zaragoza 000106621 700__ $$0(orcid)0000-0002-9543-7170$$aTejel, J.$$uUniversidad de Zaragoza 000106621 700__ $$aUrrutia, J. 000106621 7102_ $$12007$$2265$$aUniversidad de Zaragoza$$bDpto. Métodos Estadísticos$$cÁrea Estadís. Investig. Opera. 000106621 773__ $$g386 (2020), 125513 1-17$$pAppl. math. comput.$$tApplied Mathematics and Computation$$x0096-3003 000106621 8564_ $$s778752$$uhttps://zaguan.unizar.es/record/106621/files/texto_completo.pdf$$yPostprint 000106621 8564_ $$s2165692$$uhttps://zaguan.unizar.es/record/106621/files/texto_completo.jpg?subformat=icon$$xicon$$yPostprint 000106621 909CO $$ooai:zaguan.unizar.es:106621$$particulos$$pdriver 000106621 951__ $$a2021-09-02-10:10:59 000106621 980__ $$aARTICLE