Augmenting Geometric Graphs with Matchings

DOI10.1007/978-3-030-68766-3_38OpenAlexW3133714624MaRDI QIDQ5014140FDOQ5014140

Authors: Alexander Pilz, Jonathan Rollin, Lena Schlipf, André Schulz 

Publication date: 1 December 2021

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

geometric graphgraph augmentationcompatible matching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Minimum-weight triangulation is NP-hard
• Computing Simple Circuits from a Set of Line Segments is NP-Complete
• Computing simple circuits from a set of line segments
• Compatible geometric matchings
• Shortcuts for the circle
• Optimal binary space partitions in the plane
• One strike against the min-max degree triangulation problem
• Dynamic reachability in planar digraphs with one source and one sink
• Disjoint compatible geometric matchings
• Plane geometric graph augmentation: a generic perspective
• Regular augmentation of planar graphs
• Minimizing the continuous diameter when augmenting a tree with a shortcut
• Title not available (Why is that?)
• A polynomial-time algorithm for outerplanar diameter improvement

Cited In (2)

• Disjoint compatibility via graph classes
• On finding augmenting graphs

This page was built for publication: Augmenting Geometric Graphs with Matchings

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