Augmenting Geometric Graphs with Matchings

DOI10.1007/978-3-030-68766-3_38MaRDI QIDQ5014140zbMATH OpenOpenAlexFDO

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

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

Cited in

(2)

• On finding augmenting graphs
• Disjoint compatibility via graph classes

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)