On plane subgraphs of complete topological drawings

DOI10.26493/1855-3974.2226.E93MaRDI QIDQ5156010zbMATH OpenOpenAlexFDO

Authors Alfredo García Olaverri, Alexander Pilz

Publication date 14 October 2021

Published in Ars Mathematica Contemporanea (Search for Journal in Brave)

Full work available at URL https://doi.org/10.26493/1855-3974.2226.e93

zbMATH Keywords

NP-complete problemplane subgraphtopological drawing

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On the planar subdivision of a drawing of a complete graph in the plane
• scientific article; zbMATH DE number 7030516
• Unavoidable configurations in complete topological graphs
• scientific article; zbMATH DE number 2080111
• Plane augmentation of plane graphs to meet parity constraints

Cites work

• Bishellable drawings of K_n
• Combinatorial Geometry and Graph Theory
• Crossing numbers and combinatorial characterization of monotone drawings of \(K_n\)
• Density theorems for bipartite graphs and related Ramsey-type results
• Disjoint edges in complete topological graphs
• Edges without crossings in drawings of complete graphs
• Enumeration of simple complete topological graphs
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 4200260 (Why is no real title available?)
• Improved enumeration of simple topological graphs
• Many disjoint edges in topological graphs
• Minimal Triangulations of Polygonal Domains
• Shellable drawings and the cylindrical crossing number of \(K_n\)
• Simple realizability of complete abstract topological graphs in P
• The graph crossing number and its variants: a survey
• Topological graphs, empty triangles and disjoint matchings
• Unavoidable configurations in complete topological graphs
• Which crossing number is it anyway?

Cited in

(16)

• Topological Drawings of Complete Bipartite Graphs
• On the planar subdivision of a drawing of a complete graph in the plane
• Plane subgraphs in geometric complement of 2-factor and complete bipartite geometric graph
• FPT algorithms for plane completion problems
• scientific article; zbMATH DE number 7030516 (Why is no real title available?)
• Planar Lombardi Drawings for Subcubic Graphs
• Compatible spanning trees in simple drawings of \(K_n\)
• Twisted ways to find plane structures in simple drawings of complete graphs
• Towards crossing-free Hamiltonian cycles in simple drawings of complete graphs
• Twisted ways to find plane structures in simple drawings of complete graphs
• Note on disjoint faces in simple topological graphs
• Plane Hamiltonian cycles in convex drawings
• Holes in convex and simple drawings
• Plane Hamiltonian cycles in convex drawings
• Holes in convex and simple drawings
• Separable drawings: extendability and crossing-free Hamiltonian cycles

This page was built for publication: On plane subgraphs of complete topological drawings

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