Embeddings of graphs

DOI10.1016/0012-365X(92)00062-VzbMath0797.05035MaRDI QIDQ1313840

Carsten Thomassen

Publication date: 10 October 1994

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

computational complexityNP-completegraph embeddingsJordan curvegenus problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

The fiber dimension of a graph ⋮ Subexponential-time algorithms for finding large induced sparse subgraphs ⋮ Emergent time, cosmological constant and boundary dimension at infinity in combinatorial quantum gravity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rough isometries, and combinatorial approximations of geometries of non- compact Riemannian manifolds
• The converse of the Jordan curve theorem and a characterization of planar maps
• Densely embedded graphs
• Embeddings of graphs with no short noncontractible cycles
• Finite groups acting on surfaces and the genus of a group
• Triangulating a surface with a prescribed graph
• Graph minors. XIII: The disjoint paths problem
• The graph genus problem is NP-complete
• Genus of cartesian products of regular bipartite graphs
• Kuratowski's theorem
• A Link Between the Jordan Curve Theorem and the Kuratowski Planarity Criterion
• Vertex-transitive graphs and vertex-transitive maps
• The Jordan-Schonflies Theorem and the Classification of Surface
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Two-Processor Scheduling with Start-Times and Deadlines
• Computing the orientable genus of projective graphs
• Tilings of the Torus and the Klein Bottle and Vertex-Transitive Graphs on a Fixed Surface