Inserting an edge into a geometric embedding

DOI10.1016/j.comgeo.2021.101843zbMath1483.68261arXiv1807.11711OpenAlexW3211836637MaRDI QIDQ5918441

Marcel Radermacher, Ignaz Rutter

Publication date: 3 January 2022

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

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

zbMATH Keywords

crossingsdisjoint pathsstretchabilitygeometric embeddingsedge insertion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On shortest disjoint paths in planar graphs
• The directed subgraph homeomorphism problem
• The disjoint shortest paths problem
• Inserting an edge into a planar graph
• Crossing Number is NP-Complete
• Straight-Line Drawability of a Planar Graph Plus an Edge
• Drawing planar graphs with many collinear vertices
• Aligned Drawings of Planar Graphs
• Shortest Two Disjoint Paths in Polynomial Time
• Planarity Testing and Optimal Edge Insertion with Embedding Constraints
• Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
• Parameterized Algorithms

This page was built for publication: Inserting an edge into a geometric embedding