Extending simple drawings

DOI10.1007/978-3-030-35802-0_18MaRDI QIDQ2206853zbMATH OpenOpenAlexFDO

Authors Alan Arroyo, Martin Derka, Irene Parada

Publication date 26 October 2020

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

zbMATH Keywords

\(\mathsf{APX}\)-hardness\(\mathsf{NP}\)-hardnessedge insertionsimple drawings

Mathematics Subject Classification ID

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

Recommendations

• Inserting one edge into a simple drawing is hard
• Inserting one edge into a simple drawing is hard
• Extending drawings of graphs to arrangements of pseudolines
• Extending drawings of graphs to arrangements of pseudolines
• Graph Drawing

Cites work

• A Kuratowski-type theorem for planarity of partially embedded graphs
• Adding one edge to planar graphs makes crossing number and 1-planarity hard
• Augmentation Problems
• Extending convex partial drawings of graphs
• scientific article; zbMATH DE number 7030516 (Why is no real title available?)
• scientific article; zbMATH DE number 881174 (Why is no real title available?)
• Improved enumeration of simple topological graphs
• Inserting an edge into a planar graph
• ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
• Optimal binary space partitions for segments in the plane
• Partial and Constrained Level Planarity
• Planar straight-line point-set embedding of trees with partial embeddings
• Saturated simple and 2-simple topological graphs with few edges
• Saturated simple and \(k\)-simple topological graphs
• Simple realizability of complete abstract topological graphs simplified
• Some APX-completeness results for cubic graphs
• Testing Planarity of Partially Embedded Graphs
• Unavoidable configurations in complete topological graphs

Cited in

(15)

• scientific article; zbMATH DE number 7559402 (Why is no real title available?)
• Graph Drawing
• Inserting one edge into a simple drawing is hard
• Inserting one edge into a simple drawing is hard
• Extending drawings of graphs to arrangements of pseudolines
• Edge-minimum saturated \(k\)-planar drawings
• Rotation systems and simple drawings in surfaces
• Extending partial representations of circle graphs in near-linear time
• Extending partial 1-planar drawings
• Disjoint faces in drawings of the complete graph and topological Heilbronn problems
• On k-plane insertion into plane drawings
• Separable drawings: extendability and crossing-free Hamiltonian cycles
• Crossing-optimal extension of simple drawings
• The complexity of extending fair allocations of indivisible goods
• Separable drawings: extendability and crossing-free Hamiltonian cycles

This page was built for publication: Extending simple drawings

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