Simple realizability of complete abstract topological graphs in P

DOI10.1007/s00454-010-9320-xzbMath1214.05013OpenAlexW2061296093MaRDI QIDQ633211

Jan Kynčl

Publication date: 31 March 2011

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

Full work available at URL: https://doi.org/10.1007/s00454-010-9320-x

zbMATH Keywords

simple complete topological graphabstract topological graphsimple realizability

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Bad drawings of small complete graphs ⋮ Complete graph drawings up to triangle mutations ⋮ An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings ⋮ Improved enumeration of simple topological graphs ⋮ Simple realizability of complete abstract topological graphs simplified ⋮ The Complexity of Angular Resolution ⋮ Topological Drawings of Complete Bipartite Graphs ⋮ Efficient generation of different topological representations of graphs beyond-planarity ⋮ Efficient Generation of Different Topological Representations of Graphs Beyond-Planarity ⋮ On plane subgraphs of complete topological drawings ⋮ Recognition and complexity of point visibility graphs ⋮ Fixed points, Nash equilibria, and the existential theory of the reals ⋮ Crossing numbers and combinatorial characterization of monotone drawings of \(K_n\) ⋮ Induced Ramsey-type results and binary predicates for point sets ⋮ Taking a detour; or, Gioan's theorem, and pseudolinear drawings of complete graphs ⋮ Polyline drawings with topological constraints ⋮ On the Complexity of Some Geometric Problems With Fixed Parameters ⋮ Empty triangles in good drawings of the complete graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the crossing number of complete graphs
• How many ways can one draw a graph?
• On edges crossing few other edges in simple topological complete graphs
• Intersections of curves on surfaces
• String graphs. II: Recognizing string graphs is NP-hard
• String graphs requiring exponential representations
• Algorithms for Jordan curves on compact surfaces
• Proof of a conjecture of Burr, Grünbaum, and Sloane
• A special planar satisfiability problem and a consequence of its NP- completeness
• Intersection graphs of segments
• Unavoidable configurations in complete topological graphs
• On complexity of the word problem in braid groups and mapping class groups
• Recognizing string graphs is decidable
• Decidability of string graphs
• Noncrossing Subgraphs in Topological Layouts
• Simultaneous Graph Embeddings with Fixed Edges
• Complexity of Some Geometric and Topological Problems
• Relations Between Crossing Numbers of Complete and Complete Bipartite Graphs
• The Complexity of Several Realizability Problems for Abstract Topological Graphs
• Graph-Theoretic Concepts in Computer Science
• Enumeration of simple complete topological graphs
• Recognizing string graphs in NP