Plane augmentation of plane graphs to meet parity constraints
From MaRDI portal
Publication:2656724
DOI10.1016/j.amc.2020.125513zbMath1497.05052arXiv2007.11863OpenAlexW3042824509MaRDI QIDQ2656724
Jorge Urrutia, J. C. Catana, Alfredo Daniel Garcia, F. 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
augmentation problemsplane geometric graphsparity constraints\( \mathcal{NP} \)-complete problemsmaximal outerplane graphsplane topological graphs
Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Unnamed Item
- Unnamed Item
- Euler index in uncertain graph
- Parity-constrained triangulations with Steiner points
- Parameterized complexity of even/odd subgraph problems
- Augmenting the edge connectivity of planar straight line graphs to three
- Connectivity augmentation in planar straight line graphs
- Editing to Eulerian graphs
- Compatible geometric matchings
- Augmenting the connectivity of geometric graphs
- Minimum block containing a given graph
- Linear transformation distance for bichromatic matchings
- Disjoint compatible geometric matchings
- Minimum weight connectivity augmentation for planar straight-line graphs
- Supereulerian digraphs with given diameter
- Geometric biplane graphs. II: Graph augmentation
- Plane graphs with parity constraints
- Parameterized complexity of Eulerian deletion problems
- Compatible spanning trees
- Plane Geometric Graph Augmentation: A Generic Perspective
- Augmenting Undirected Node-Connectivity by One
- Augmenting the Connectivity of Planar and Geometric Graphs
- BOUNDED LENGTH, 2-EDGE AUGMENTATION OF GEOMETRIC PLANAR GRAPHS
- Planar Formulae and Their Uses
- Augmentation Problems
- The spanning subgraphs of eulerian graphs
- Matching, Euler tours and the Chinese postman
- A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2
- Efficient Algorithms for Eulerian Extension and Rural Postman
- How to Draw a Graph
