Simple realizability of complete abstract topological graphs in P
From MaRDI portal
Publication:633211
DOI10.1007/s00454-010-9320-xzbMath1214.05013OpenAlexW2061296093MaRDI QIDQ633211
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
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
