Extending simple drawings

DOI10.1007/978-3-030-35802-0_18OpenAlexW2991316574MaRDI QIDQ2206853

Martin Derka, Irene Parada, Alan Arroyo

Publication date: 26 October 2020

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

zbMATH Keywords

edge insertion\(\mathsf{APX}\)-hardness\(\mathsf{NP}\)-hardnesssimple drawings

Mathematics Subject Classification ID

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

Related Items (2)

Unnamed Item ⋮ Inserting one edge into a simple drawing is hard

Cites Work

• Unnamed Item
• Unnamed Item
• Extending convex partial drawings of graphs
• Improved enumeration of simple topological graphs
• Planar straight-line point-set embedding of trees with partial embeddings
• Unavoidable configurations in complete topological graphs
• Some APX-completeness results for cubic graphs
• Inserting an edge into a planar graph
• A Kuratowski-type theorem for planarity of partially embedded graphs
• Saturated simple and \(k\)-simple topological graphs
• Simple Realizability of Complete Abstract Topological Graphs Simplified
• Augmentation Problems
• Partial and Constrained Level Planarity
• Saturated simple and 2-simple topological graphs with few edges
• Testing Planarity of Partially Embedded Graphs
• OPTIMAL BINARY SPACE PARTITIONS FOR SEGMENTS IN THE PLANE
• Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
• ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
• Extending upward planar graph drawings

This page was built for publication: Extending simple drawings