Embedding graphs into two-dimensional simplicial complexes

DOI10.4230/LIPICS.SOCG.2018.27MaRDI QIDQ5115795zbMATH OpenFDO

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

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)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 986974 (Why is no real title available?)
• scientific article; zbMATH DE number 412172 (Why is no real title available?)
• scientific article; zbMATH DE number 5485473 (Why is no real title available?)
• scientific article; zbMATH DE number 1241838 (Why is no real title available?)
• scientific article; zbMATH DE number 1156577 (Why is no real title available?)
• scientific article; zbMATH DE number 2079390 (Why is no real title available?)
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• Combinatorial optimization of cycles and bases
• Deleting vertices to graphs of bounded genus
• Genus g Graphs Have Pagenumber O(√g)
• Graph Drawing
• Graph minors. XIII: The disjoint paths problem
• Graph-encoded maps
• Graphs on surfaces
• HOMEOMORPHISM OF 2-COMPLEXES IS EQUIVALENT TO GRAPH ISOMORPHISM
• Hardness of embedding simplicial complexes in R^d
• Polynomial-time computation of homotopy groups and Postnikov systems in fixed dimension
• Testing Planarity of Partially Embedded Graphs
• Testing graph isotopy on surfaces
• The graph genus problem is NP-complete
• The word problem
• Transforming curves on surfaces
• Transforming curves on surfaces redux

Cited in

(5)

• On the links of vertices in simplicial \(d\)-complexes embeddable in the Euclidean \(2d\)-space
• On the complexity of graph embeddings
• Deciding whether a grid is a topological subgraph of a planar graph is NP-complete
• scientific article; zbMATH DE number 4156463 (Why is no real title available?)
• scientific article; zbMATH DE number 7662167 (Why is no real title available?)

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)