Embedding graphs into two-dimensional simplicial complexes

DOI10.4230/LIPICS.SOCG.2018.27zbMATH Open1489.68187arXiv1803.07032MaRDI QIDQ5115795FDOQ5115795

Authors: Éric Colin de Verdière, Thomas Magnard, Bojan Mohar 

Publication date: 18 August 2020

Full work available at URL: https://arxiv.org/abs/1803.07032

Recommendations

• scientific article; zbMATH DE number 7662167
• scientific article
• scientific article; zbMATH DE number 7051255
• Hardness of embedding simplicial complexes in \(\mathbb R^d\)
• On the complexity of graph embeddings

zbMATH Keywords

graphsurfacecomputational topologysimplicial complexembedding

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Simplicial sets and complexes in algebraic topology (55U10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Graph minors. XIII: The disjoint paths problem
• Graphs on surfaces
• The graph genus problem is NP-complete
• Title not available (Why is that?)
• The word problem
• Title not available (Why is that?)
• Graph-encoded maps
• Title not available (Why is that?)
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• Title not available (Why is that?)
• Genus g Graphs Have Pagenumber O(√g)
• Testing Planarity of Partially Embedded Graphs
• Polynomial-Time Computation of Homotopy Groups and Postnikov Systems in Fixed Dimension
• Hardness of embedding simplicial complexes in \(\mathbb R^d\)
• Title not available (Why is that?)
• Embeddability in the 3-Sphere Is Decidable
• Title not available (Why is that?)
• Transforming curves on surfaces
• Combinatorial optimization of cycles and bases
• Deleting vertices to graphs of bounded genus
• Testing graph isotopy on surfaces
• Transforming Curves on Surfaces Redux
• Graph Drawing
• HOMEOMORPHISM OF 2-COMPLEXES IS EQUIVALENT TO GRAPH ISOMORPHISM

Cited In (4)

• On the links of vertices in simplicial \(d\)-complexes embeddable in the Euclidean \(2d\)-space
• On the complexity of graph embeddings
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: Embedding graphs into two-dimensional simplicial complexes

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