Inserting one edge into a simple drawing is hard

DOI10.1007/s00454-022-00394-9OpenAlexW4288106882WikidataQ114229301 ScholiaQ114229301MaRDI QIDQ5925627

Birgit Vogtenhuber, Irene Parada, Raimund Seidel, Tilo Wiedera, Alan Arroyo, Fabian Klute

Publication date: 9 March 2023

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-022-00394-9

zbMATH Keywords

algorithmslower boundsdiscrete geometrygraph drawingarrangements of pseudocirclessimple drawings

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extending convex partial drawings of graphs
• Improved enumeration of simple topological graphs
• Extending partial representations of proper and unit interval graphs
• The partial visibility representation extension problem
• Planar straight-line point-set embedding of trees with partial embeddings
• Point-set embeddings of trees with given partial drawings
• Inserting an edge into a planar graph
• Extending simple drawings
• Saturated simple and \(k\)-simple topological graphs
• Extending partial representations of subclasses of chordal graphs
• Extension spaces of oriented matroids
• Extending partial representations of interval graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Extending Partial Representations of Function Graphs and Permutation Graphs
• Contact Representations of Planar Graphs: Extending a Partial Representation is Hard
• Research Problems in Discrete Geometry
• Partial and Constrained Level Planarity
• Crossing Numbers of Graphs
• Saturated simple and 2-simple topological graphs with few edges
• Levi's Lemma, pseudolinear drawings of , and empty triangles
• Testing Planarity of Partially Embedded Graphs
• Extending Partial Orthogonal Drawings
• Extending partial representations of circle graphs
• Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
• ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
• Drawing Graphs in the Plane with a Prescribed Outer Face and Polynomial Area
• Extending upward planar graph drawings
• Inserting an edge into a geometric embedding

This page was built for publication: Inserting one edge into a simple drawing is hard