Simple realizability of complete abstract topological graphs in P
From MaRDI portal
Publication:633211
DOI10.1007/S00454-010-9320-XzbMATH Open1214.05013OpenAlexW2061296093MaRDI QIDQ633211FDOQ633211
Authors: 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
Recommendations
- The Complexity of Several Realizability Problems for Abstract Topological Graphs
- Simple realizability of complete abstract topological graphs simplified
- Simple realizability of complete abstract topological graphs simplified
- scientific article; zbMATH DE number 7030516
- Enumeration of simple complete topological graphs
Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10)
Cites Work
- Intersection graphs of segments
- A special planar satisfiability problem and a consequence of its NP- completeness
- Title not available (Why is that?)
- Enumeration of simple complete topological graphs
- Proof of a conjecture of Burr, Grünbaum, and Sloane
- Complexity of some geometric and topological problems
- Intersections of curves on surfaces
- Title not available (Why is that?)
- Unavoidable configurations in complete topological graphs
- Title not available (Why is that?)
- Graph-Theoretic Concepts in Computer Science
- Recognizing string graphs in NP
- How many ways can one draw a graph?
- On complexity of the word problem in braid groups and mapping class groups
- Relations Between Crossing Numbers of Complete and Complete Bipartite Graphs
- Simultaneous Graph Embeddings with Fixed Edges
- String graphs. II: Recognizing string graphs is NP-hard
- String graphs requiring exponential representations
- Decidability of string graphs
- Recognizing string graphs is decidable
- On the crossing number of complete graphs
- On edges crossing few other edges in simple topological complete graphs
- Algorithms for Jordan curves on compact surfaces
- Title not available (Why is that?)
- Noncrossing Subgraphs in Topological Layouts
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The Complexity of Several Realizability Problems for Abstract Topological Graphs
Cited In (23)
- Bad drawings of small complete graphs
- Rotation systems and simple drawings in surfaces
- Empty triangles in good drawings of the complete graph
- Complete graph drawings up to triangle mutations
- An optimal algorithm for reconstructing point set order types from radial orderings
- Efficient generation of different topological representations of graphs beyond-planarity
- Taking a detour; or, Gioan's theorem, and pseudolinear drawings of complete graphs
- Different types of isomorphisms of drawings of complete multipartite graphs
- Topological Drawings of Complete Bipartite Graphs
- Induced Ramsey-type results and binary predicates for point sets
- On the complexity of some geometric problems with fixed parameters
- The Complexity of Several Realizability Problems for Abstract Topological Graphs
- Crossing numbers and combinatorial characterization of monotone drawings of \(K_n\)
- Polyline drawings with topological constraints
- The Complexity of Angular Resolution
- On rectilinear topological graphs
- Simple realizability of complete abstract topological graphs simplified
- Recognition and complexity of point visibility graphs
- On plane subgraphs of complete topological drawings
- Improved enumeration of simple topological graphs
- Fixed points, Nash equilibria, and the existential theory of the reals
- Simple realizability of complete abstract topological graphs simplified
- Efficient generation of different topological representations of graphs beyond-planarity
This page was built for publication: Simple realizability of complete abstract topological graphs in P
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q633211)
