Compatible geometric matchings

DOI10.1016/j.comgeo.2008.12.005zbMath1200.05140arXiv0709.3375OpenAlexW2138849026MaRDI QIDQ924079

Clemens Huemer, Jorge Urrutia, David R. Wood, Alberto Márquez, Mikio Kano, Ferran Hurtado, Oswin Aichholzer, Adrian Dumitrescu, Sergey Bereg, Shakhar Smorodinsky, David Rappaport, Alfredo Daniel Garcia, Diane L. Souvaine

Publication date: 27 July 2009

Published in: Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

geometric graphcompatible matchingconvex-hull-connected segmentsconvexly independent segmentssegments in convex position

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

On Compatible Matchings, Plane augmentation of plane graphs to meet parity constraints, Packing 1-plane Hamiltonian cycles in complete geometric graphs, Convex Partitions with 2-Edge Connected Dual Graphs, Faster bottleneck non-crossing matchings of points in convex position, Disjoint compatibility via graph classes, Compatible spanning trees in simple drawings of \(K_n\), Disjoint compatible geometric matchings, Linear transformation distance for bichromatic matchings, Crossing-Free Perfect Matchings in Wheel Point Sets, Compatible spanning trees, Convex partitions with 2-edge connected dual graphs, On compatible matchings, Structural properties of bichromatic non-crossing matchings, Disjoint compatibility graph of non-crossing matchings of points in convex position, Flip distance to some plane configurations, Augmenting Geometric Graphs with Matchings, Bichromatic compatible matchings

Cites Work

• Unnamed Item
• Computing simple circuits from a set of line segments
• Alternating paths along axis-parallel segments
• Augmenting the connectivity of geometric graphs
• Alternating paths through disjoint line segments
• Transforming spanning trees: A lower bound
• Transforming spanning trees and pseudo-triangulations
• Hamiltonian triangulations and circumscribing polygons of disjoint line segments
• On a counterexample to a conjecture of Mirzaian
• Canonical theorems for convex sets
• On circumscribing polygons for line segments
• Segment endpoint visibility graphs are Hamiltonian
• Erdős-Szekeres-type theorems for segments and noncrossing convex sets
• Graph orientations with edge-connection and parity constraints
• Graphs of triangulations and perfect matchings
• Convexly independent sets
• Computing Simple Circuits from a Set of Line Segments is NP-Complete
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• A generalization of the Erdös-Szekeres convex n-gon theorem.
• Algorithm Theory - SWAT 2004
• Finding convex sets in convex positions
• Every set of disjoint line segments admits a binary tree
• An orientation theorem with parity conditions
• Sequences of spanning trees and a fixed tree theorem